In the Stone Game II problem, you are given an array piles where piles[i] is the number of stones in the i-th pile. Two players, Alice and Bob, take turns. Alice always goes first.
M = 1.X piles, where 1 ≤ X ≤ 2M.M becomes max(M, X).The goal is to determine the maximum number of stones Alice can get.
Constraints:
1 ≤ piles.length ≤ 1001 ≤ piles[i] ≤ 10^4To solve this problem, we need to simulate the choices made by both Alice and Bob, each trying to maximize their own score while minimizing the opponent's. The naive approach would be to try every possible move for both players at every turn, but this quickly becomes infeasible due to the exponential number of possibilities.
The key insight is to recognize that the problem has optimal substructure—the best move at any point depends only on the current position and the value of M. This makes the problem suitable for dynamic programming with memoization.
Instead of simulating both players in a brute-force manner, we can use recursion to compute the best outcome from any state, storing results to avoid redundant calculations. By thinking in terms of "what's the most stones the current player can get from this position," we can build up the solution efficiently.
We'll use a top-down dynamic programming approach with memoization. Here's a step-by-step breakdown:
i: The current index in piles (where we are in the array).M: The current value of M.i with M.
i >= len(piles), there are no more stones to take, so return 0.
X (from 1 to 2M), try taking the next X piles (if available), summing the stones, and recursively solving for the opponent starting from i + X and M' = max(M, X).
X, Alice's total = stones taken now + (total stones remaining - best Bob can get).piles.
(i, M) pair to avoid redundant calculations.
This approach ensures that each subproblem is solved only once, and we always make optimal decisions at each step.
Let's use piles = [2,7,9,4,4] as an example.
M = 1. She can take 1 or 2 piles.
M = 1.M = 2.M = 2, so he can take up to 4 piles (but only 3 left).2M moves, and M can double each time. This leads to a huge number of recursive calls.
O(N^2) where N is the number of piles. This is because there are N possible start indices and up to N possible values of M.
O(N^2) since for each state, we loop through at most 2M ≤ 2N choices, but the total number of subproblems is bounded by N^2 due to memoization.
O(N^2) for the memoization table and O(N) for the suffix sum array.
The Stone Game II problem is a classic example of using dynamic programming to break down a complex, two-player game into manageable subproblems. By carefully defining our state and using memoization, we avoid redundant work and ensure optimal play. The approach leverages recursion, dynamic programming, and a clear understanding of how to model two-player games where both sides play optimally. The final solution is both efficient and elegant, guaranteeing Alice the maximum stones she can secure.
from functools import lru_cache
class Solution:
def stoneGameII(self, piles):
n = len(piles)
# Suffix sum: total stones from i to end
suffix_sum = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix_sum[i] = piles[i] + suffix_sum[i + 1]
@lru_cache(None)
def dp(i, M):
if i >= n:
return 0
max_stones = 0
for X in range(1, min(2 * M, n - i) + 1):
# Opponent's best is the rest minus what we get after their optimal move
max_stones = max(max_stones, suffix_sum[i] - dp(i + X, max(M, X)))
return max_stones
return dp(0, 1)
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution {
public:
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector<int> suffixSum(n + 1, 0);
for (int i = n - 1; i >= 0; --i)
suffixSum[i] = piles[i] + suffixSum[i + 1];
vector<vector<int>> memo(n, vector<int>(n + 1, -1));
function<int(int, int)> dp = [&](int i, int M) {
if (i >= n) return 0;
if (memo[i][M] != -1) return memo[i][M];
int maxStones = 0;
for (int X = 1; X <= min(2 * M, n - i); ++X) {
maxStones = max(maxStones, suffixSum[i] - dp(i + X, max(M, X)));
}
return memo[i][M] = maxStones;
};
return dp(0, 1);
}
};
import java.util.*;
class Solution {
public int stoneGameII(int[] piles) {
int n = piles.length;
int[] suffixSum = new int[n + 1];
for (int i = n - 1; i >= 0; --i) {
suffixSum[i] = piles[i] + suffixSum[i + 1];
}
int[][] memo = new int[n][n + 1];
for (int[] row : memo)
Arrays.fill(row, -1);
return dp(0, 1, piles, suffixSum, memo);
}
private int dp(int i, int M, int[] piles, int[] suffixSum, int[][] memo) {
int n = piles.length;
if (i >= n) return 0;
if (memo[i][M] != -1) return memo[i][M];
int maxStones = 0;
for (int X = 1; X <= Math.min(2 * M, n - i); ++X) {
maxStones = Math.max(maxStones, suffixSum[i] - dp(i + X, Math.max(M, X), piles, suffixSum, memo));
}
memo[i][M] = maxStones;
return maxStones;
}
}
/**
* @param {number[]} piles
* @return {number}
*/
var stoneGameII = function(piles) {
const n = piles.length;
const suffixSum = Array(n + 1).fill(0);
for (let i = n - 1; i >= 0; --i) {
suffixSum[i] = piles[i] + suffixSum[i + 1];
}
const memo = Array.from({length: n}, () => Array(n + 1).fill(-1));
function dp(i, M) {
if (i >= n) return 0;
if (memo[i][M] !== -1) return memo[i][M];
let maxStones = 0;
for (let X = 1; X <= Math.min(2 * M, n - i); ++X) {
maxStones = Math.max(maxStones, suffixSum[i] - dp(i + X, Math.max(M, X)));
}
memo[i][M] = maxStones;
return maxStones;
}
return dp(0, 1);
};