Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1140.html
1140. Stone Game II (Medium)
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 <= 1001 <= piles[i] <= 10 ^ 4
Related Topics:
Dynamic Programming
Solution 1. DP
Let dp[i][m] be optimal result Alex can get on subarray A[i..(N-1)] and with inital M = m. It’s a pair<int, int> where the first element is the stones Alex can get and the second is the stones Lee can get.
dp[i][m] = <p.second + A[i] + ... + A[i + x - 1], p.first>
where p = dp[i + x][max(m, x)], 1 <= x <= 2m
The answer is dp[0][1].first.
// OJ: https://leetcode.com/problems/stone-game-ii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
pair<int, int> dp[101][101] = {};
int presum[101] = {};
pair<int, int> dfs(vector<int> &A, int i, int M) {
if (i == A.size()) return {0, 0};
if (dp[i][M].first != 0) return dp[i][M];
for (int x = 1; x <= min((int)A.size() - i, 2 * M); ++x) {
auto p = dfs(A, i + x, max(M, x));
int sum = presum[i + x] - presum[i];
if (p.second + sum > dp[i][M].first) dp[i][M] = { p.second + sum, p.first };
}
return dp[i][M];
}
public:
int stoneGameII(vector<int>& A) {
partial_sum(begin(A), end(A), presum + 1);
return dfs(A, 0, 1).first;
}
};
Solution 2. DP
// OJ: https://leetcode.com/problems/stone-game-ii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
int dp[101][101] = {}, sum[101] = {};
int dfs(vector<int> &A, int i, int M) {
if (i == A.size()) return 0;
if (dp[i][M]) return dp[i][M];
for (int X = 1; X <= 2 * M && i + X <= A.size(); ++X) dp[i][M] = max(dp[i][M], sum[A.size()] - sum[i] - dfs(A, i + X, max(M, X)));
return dp[i][M];
}
public:
int stoneGameII(vector<int>& A) {
partial_sum(begin(A), end(A), sum + 1);
return dfs(A, 0, 1);
}
};
-
class Solution { public int stoneGameII(int[] piles) { int length = piles.length; int[] rearSums = new int[length]; rearSums[length - 1] = piles[length - 1]; for (int i = length - 2; i >= 0; i--) rearSums[i] = rearSums[i + 1] + piles[i]; int[][] dp = new int[length + 1][length]; for (int i = length - 1; i >= 0; i--) { for (int j = length - 1; j >= 0; j--) { int maxStones = 0; int startIndex = i, endIndex = Math.min(length - 1, 2 * (j + 1) + i - 1); for (int k = startIndex; k <= endIndex; k++) { int maxTiles = Math.max(k - i + 1, j + 1); maxStones = Math.max(maxStones, rearSums[i] - dp[k + 1][maxTiles - 1]); } dp[i][j] = maxStones; } } return dp[0][0]; } } ############ class Solution { private int[] s; private Integer[][] f; private int n; public int stoneGameII(int[] piles) { n = piles.length; s = new int[n + 1]; f = new Integer[n][n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + piles[i]; } return dfs(0, 1); } private int dfs(int i, int m) { if (m * 2 >= n - i) { return s[n] - s[i]; } if (f[i][m] != null) { return f[i][m]; } int res = 0; for (int x = 1; x <= m * 2; ++x) { res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x))); } return f[i][m] = res; } } -
// OJ: https://leetcode.com/problems/stone-game-ii/ // Time: O(N^2) // Space: O(N^2) class Solution { pair<int, int> dp[101][101] = {}; int presum[101] = {}; pair<int, int> dfs(vector<int> &A, int i, int M) { if (i == A.size()) return {0, 0}; if (dp[i][M].first != 0) return dp[i][M]; for (int x = 1; x <= min((int)A.size() - i, 2 * M); ++x) { auto p = dfs(A, i + x, max(M, x)); int sum = presum[i + x] - presum[i]; if (p.second + sum > dp[i][M].first) dp[i][M] = { p.second + sum, p.first }; } return dp[i][M]; } public: int stoneGameII(vector<int>& A) { partial_sum(begin(A), end(A), presum + 1); return dfs(A, 0, 1).first; } }; -
class Solution: def stoneGameII(self, piles: List[int]) -> int: @cache def dfs(i, m): if m * 2 >= n - i: return s[-1] - s[i] res = 0 for x in range(1, m << 1 | 1): t = s[-1] - s[i] - dfs(i + x, max(m, x)) res = max(res, t) return res s = list(accumulate(piles, initial=0)) n = len(piles) return dfs(0, 1) -
func stoneGameII(piles []int) int { n := len(piles) s := make([]int, n+1) f := make([][]int, n+1) for i, x := range piles { s[i+1] = s[i] + x f[i] = make([]int, n+1) } var dfs func(i, m int) int dfs = func(i, m int) int { if m*2 >= n-i { return s[n] - s[i] } if f[i][m] > 0 { return f[i][m] } f[i][m] = 0 for x := 1; x <= m<<1; x++ { f[i][m] = max(f[i][m], s[n]-s[i]-dfs(i+x, max(m, x))) } return f[i][m] } return dfs(0, 1) } func max(a, b int) int { if a > b { return a } return b } -
function stoneGameII(piles: number[]): number { const n = piles.length; const f = Array.from({ length: n }, _ => new Array(n + 1).fill(0)); const s = new Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] + piles[i]; } const dfs = (i: number, m: number) => { if (m * 2 >= n - i) { return s[n] - s[i]; } if (f[i][m]) { return f[i][m]; } let res = 0; for (let x = 1; x <= m * 2; ++x) { res = Math.max(res, s[n] - s[i] - dfs(i + x, Math.max(m, x))); } return (f[i][m] = res); }; return dfs(0, 1); }