LeetCode: Stone Game II Posted on August 5, 2019July 26, 2020 by braindenny Stone Game II Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #game, #minimax, dynamicprogramming, recursive 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