Pattern Guide
Stone Game & Minimax DP
"Both players play optimally. DP for competitive game results and optimal values."
Stone game problems involve two players alternately making optimal moves. Key insight: dp[i][j] = maximum score advantage (current player minus opponent) achievable from stones[i..j]. Transition: current player picks from either end, opponent plays optimally on the remainder. For simple cases, mathematical tricks (parity, prefix sums) give O(1). Complex variants need true DP or alpha-beta pruning.
Problems you can solve with this pattern
4 problems · click any to start solving
// Stone Game I — can first player always win? (trivially yes for even n)
// Stone Game DP: dp[i][j] = score advantage for current player
function stoneGameAdvantage(piles) {
const n = piles.length;
const dp = Array.from({length: n}, (_, i) => [...piles]); // dp[i][i] = piles[i]
// Initialize diagonal: dp[i][i] = piles[i] (already done)
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Math.max(
piles[i] - dp[i+1][j], // take left, opponent gets dp[i+1][j]
piles[j] - dp[i][j-1] // take right, opponent gets dp[i][j-1]
);
}
}
return dp[0][n-1]; // >= 0 means first player wins or ties
}Stone game DP: dp[i][j] = score advantage for current player from range [i..j]. dp[i][i] = piles[i]. For j > i: dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]). If dp[0][n-1] >= 0, first player wins. Note: score advantage = your_score - opponent_score. Since opponent plays optimally on the subproblem, their max advantage from remaining = dp[...][...].
// Stone Game I — can first player always win? (trivially yes for even n)
// Stone Game DP: dp[i][j] = score advantage for current player
function stoneGameAdvantage(piles) {
const n = piles.length;
const dp = Array.from({length: n}, (_, i) => [...piles]); // dp[i][i] = piles[i]
// Initialize diagonal: dp[i][i] = piles[i] (already done)
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Math.max(
piles[i] - dp[i+1][j], // take left, opponent gets dp[i+1][j]
piles[j] - dp[i][j-1] // take right, opponent gets dp[i][j-1]
);
}
}
return dp[0][n-1]; // >= 0 means first player wins or ties
}Two-player game patterns:
- Take from ends: interval DP, O(n²)
- Take any perfect square: 1D DP, O(n√n)
- Take from stack in runs: DP from right, O(n)
- Nim game: XOR of pile sizes
Reduction to Sprague-Grundy: For impartial games (both players have same moves), compute Grundy values. Non-zero = first player wins.