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 <= 100
• 1 <= 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.first.

// OJ: https://leetcode.com/problems/stone-game-ii/

// Time: O(N^2)
// Space: O(N^2)
class Solution {
pair<int, int> dp = {};
int presum = {};
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 = {}, sum = {};
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);
}
};


Java

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;
}
}