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] <= 104
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
@cache
def dfs(i, m):
if m * 2 >= n - i:
return s[n] - s[i]
return max(
s[n] - s[i] - dfs(i + x, max(m, x)) for x in range(1, m << 1 | 1)
)
n = len(piles)
s = list(accumulate(piles, initial=0))
return dfs(0, 1)class Solution:
def stoneGameII(self, piles: List[int]) -> int:
@cache
def dfs(i: int, m: int = 1) -> int:
if i >= len(piles):
return 0
t = inf
for x in range(1, m << 1 | 1):
t = min(t, dfs(i + x, max(m, x)))
return s[-1] - s[i] - t
s = list(accumulate(piles, initial=0))
return dfs(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;
}
}class Solution {
public:
int stoneGameII(vector<int>& piles) {
int n = piles.size();
int s[n + 1];
s[0] = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + piles[i];
}
int f[n][n + 1];
memset(f, 0, sizeof f);
function<int(int, int)> dfs = [&](int i, int m) -> int {
if (m * 2 >= n - i) {
return s[n] - s[i];
}
if (f[i][m]) {
return f[i][m];
}
int res = 0;
for (int x = 1; x <= m << 1; ++x) {
res = max(res, s[n] - s[i] - dfs(i + x, max(x, m)));
}
return f[i][m] = res;
};
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);
}