Alice and Bob 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.
Alice and Bob take turns, with Alice 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 Alice and Bob play optimally, return the maximum number of stones Alice can get.
Example 1:
Input: piles = [2,7,9,4,4] Output: 10 Explanation: If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.
Example 2:
Input: piles = [1,2,3,4,5,100] Output: 104
Constraints:
1 <= piles.length <= 1001 <= piles[i] <= 104class Solution {
int n;
public int stoneGameII(int[] piles) {
n = piles.length;
int runningSum = 0;
int[] suffixSum = new int[n];
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
suffixSum[i] = piles[i] + runningSum;
runningSum = suffixSum[i];
}
// System.out.println(Arrays.toString(suffixSum));
return solve(suffixSum, dp, 0, 1);
}
private int solve(int[] suffixSum, int[][] dp, int lt, int m) {
if (lt + 2 * m >= n)
return suffixSum[lt];
if (dp[lt][m] > 0)
return dp[lt][m];
int nextMove = suffixSum[lt];
for (int x = 1; x <= 2 * m && lt + x < n; x++)
nextMove = Math.min(nextMove, solve(suffixSum, dp, lt + x, Math.max(m, x)));
// System.out.println(nextMove);
return dp[lt][m] = suffixSum[lt] - nextMove;
}
}