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 <= 1001 <= 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]
}
}
Input
Output
#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)
Input
Output
#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];
}
}
}
Input
Output