LeetCode: Stone Game II

Posted on August 5, 2019July 26, 2020 by braindenny

Stone Game II

Similar Problems:

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/stone-game-ii
// Basic Ideas: minimax
//
//   dp(i, m): when there are piles[i:] to choose. And m is the threshold.
//   The result would be dp(0, 1) 
//
//   dp(i, j) = 
//           max(sufsum[i] - dp[i+X][max(j, X)])
//            loop: 1<=X<=2j
//
// Complexity: Time O(n^3), Space O(n^2)
/*
2, 7, 9, 4, 4

dp(0, 1) = 
    max(sufsum[0] - dp(1, 1), // take one
        sufsum[0] - dp(2, 2)) // take two
*/
func min(x, y int) int {
    if x<y {
        return x
    } else {
        return y
    }
}

func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func dfs(sufsum []int, i int, j int, m map[[2]int]int) int {
    if i>=len(sufsum) {
        return 0
    }
    if v, ok := m[[2]int{i, j}]; ok {
        return v
    }
    res := sufsum[i]
    v := 1<<32-1
    for k:=1; k<=2*j; k++ {
        if v == 0 {
            break
        }
        v = min(v, dfs(sufsum, i+k, max(j, k), m))
    }
    if v == 1<<32-1 {
        v = 0
    }
    res -= v
    m[[2]int{i, j}] = res
    return res
}

func stoneGameII(piles []int) int {
    m := map[[2]int]int{}
    sufsum := make([]int, len(piles))
    sum := 0
    for j:=len(piles)-1; j>=0; j-- {
        sum += piles[j]
        sufsum[j] = sum
    }
    res := dfs(sufsum, 0, 1, m)
    return res
}

Post Views: 0