##### 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 <= 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[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);
}