## Algorithm

Problem Name: 1140. Stone Game II

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 <= 100`
• `1 <= piles[i] <= 104`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const stoneGameII = function(piles) {
let sums = [] //the sum from piles[i] to the end
let hash = []
if (piles == null || piles.length == 0) return 0
let n = piles.length
sums = new Array(n)
sums[n - 1] = piles[n - 1]
for (let i = n - 2; i >= 0; i--) {
sums[i] = sums[i + 1] + piles[i] //the sum from piles[i] to the end
}

hash = Array.from({ length: n }, () => new Array(n).fill(0))
return helper(piles, 0, 1)

function helper(a, i, M) {
if (i == a.length) return 0
if (2 * M >= a.length - i) {
return sums[i]
}
if (hash[i][M] != 0) return hash[i][M]
let min = Number.MAX_SAFE_INTEGER //the min value the next player can get
for (let x = 1; x  < = 2 * M; x++) {
min = Math.min(min, helper(a, i + x, Math.max(M, x)))
}
hash[i][M] = sums[i] - min //max stones = all the left stones - the min stones next player can get
return hash[i][M]
}
}
``````
Copy The Code &

Input

cmd
piles = [2,7,9,4,4]

Output

cmd
10

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def stoneGameII(self, A: List[int]) -> int:
N = len(A)
for i in range(N - 2, -1, -1):
A[i] += A[i + 1]
from functools import lru_cache
@lru_cache(None)
def dp(i, m):
if i + 2 * m >= N: return A[i]
return A[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
return dp(0, 1)
``````
Copy The Code &

Input

cmd
piles = [2,7,9,4,4]

Output

cmd
10

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _1140_StoneGameII
{
public int StoneGameII(int[] piles)
{
var N = piles.Length;
var sum = 0;
var sums = new int[N];
for (int i = N - 1; i >= 0; i--)
{
sum += piles[i];
sums[i] = sum;
}

var dp = new int[N, N];
return Play(piles, sums, dp, 0, 1);
}

private int Play(int[] piles, int[] sums, int[,] dp, int index, int M)
{
var N = piles.Length;
if (index >= N) return 0;
if (M * 2 >= N - index) return sums[index];
if (dp[index, M] != 0) return dp[index, M];

for (int i = 1; i  < = Math.Min(N, 2 * M) && index + i < N; i++)
{
var taken = sums[index] - sums[index + i];
var remain = sums[index + i] - Play(piles, sums, dp, index + i, Math.Max(M, i));
dp[index, M] = Math.Max(dp[index, M], taken + remain);
}

return dp[index, M];
}
}
}
``````
Copy The Code &

Input

cmd
piles = [1,2,3,4,5,100]

Output

cmd
104