p79 — Stone Game II

Source: LeetCode 1140 · Medium (functionally Hard) · Topics: Game DP, Minimax, Suffix Sums Companies (2024–2025): Google (high), Amazon (medium), Meta (medium) Loop position: The minimax game DP with a dynamic M parameter. State (i, M); suffix sums collapse “rest of game” into O(1). Tests dynamic state design.

1. Quick Context

Piles[i] stones. Two players alternate. On each turn, current player takes the first X piles where 1 ≤ X ≤ 2M. Then M = max(M, X). Initial M = 1. Both play optimally to maximize their own stones. Alice goes first. Return Alice’s max stones.

Game DP: dp[i][M] = max stones the current player can collect from piles i..n-1 with parameter M. Suffix sum suf[i] = sum(piles[i:]). Recurrence:

dp[i][M] = max over x in 1..min(2M, n-i) of (suf[i] - dp[i+x][max(M, x)])

(Current player takes the first x piles → suf[i] - suf[i+x]; opponent then plays optimally from state (i+x, max(M,x)) collecting dp[i+x][max(M,x)]; so current player gets total = my immediate take + (remaining suffix minus opponent’s optimal). Cleaner form: my total = suf[i] - opponent’s optimal = suf[i] - dp[i+x][max(M,x)].)

Answer: dp[0][1].

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/stone-game-ii/

STOP. 45-min timer. The “my-take = suffix - opponent’s-optimal” identity is the trick.

3. Prerequisite Concepts

  • Minimax on games.
  • Suffix sums for O(1) “rest of game total”.
  • State design with a dynamically-updated parameter (M).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Alternate-turn game where each player takes 1..2M front piles; M grows. Maximize own total.

2. Clarify: Both optimal? Yes. M can exceed n? min(2M, n-i) caps it.

3. Examples: piles=[2,7,9,4,4] → Alice 10. piles=[1,2,3,4,5,100] → Alice 104.

5. Brute: Recursive minimax without memo. Exponential.

6. Target: O(n²) (states: n × n M values; transitions O(n)).

7. Pattern: Zero-sum game DP with suffix-sum identity.

8. Develop: see solution.py.

9. Test: monotonic increasing (last-pile-grab wins); small inputs.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why dp[i][M] is “current player’s max” not “Alice’s max”

Symmetry: roles flip each turn but objective is “maximize my own”. Track from current-player POV; alternate naturally via recursion.

6.2 The suffix-sum identity

If from state (i, M) the current player takes x piles, they get suf[i] - suf[i+x]. Opponent then plays state (i+x, max(M,x)) and collects dp[i+x][max(M,x)] for themselves. Total in suffix from i = suf[i] = my immediate take + opponent’s take + my future take. Rearranging: my total from (i,M) = (suf[i] - suf[i+x]) + (suf[i+x] - dp[i+x][max(M,x)]) = suf[i] - dp[i+x][max(M,x)]. The middle two cancel.

6.3 Why M can be capped at n

M starts at 1 and grows by at most n per turn. Practically M ≤ n suffices since 2M ≥ 2n already lets the player take everything. Cap M at n in the table.

6.4 Base case

i == n: no piles left; dp = 0. Also if 2M >= n - i: current player can take everything → dp[i][M] = suf[i].

6.5 Memoization order

Top-down with @lru_cache is cleanest. Bottom-up: iterate i from n down to 0; M from 1 to n.

6.6 Family: zero-sum game DPs

  • LC 877 Stone Game (take from either end; constant difference DP).
  • LC 1140 Stone Game II (this one; dynamic M).
  • LC 1406 Stone Game III (take 1, 2, or 3 from front; minimax).
  • LC 1510 Stone Game IV (take square number; win/lose only, not score).
  • LC 1690 Stone Game VII (alternating with score on remaining sum).

All share the “my total = total - opponent’s optimal” identity.

7. Anti-Pattern Analysis

  1. Track Alice’s total directly — confuses player roles; harder to recurse.
  2. Forget to update M = max(M, x) — game rule violated.
  3. No suffix sum — recompute “rest of pile total” each call; quadratic factor explodes.
  4. Forget the 2M ≥ n - i base case — extra work; correctness preserved but slower.
  5. Off-by-one on the 1..2M range — must include x = 2M.
  6. Try to track both players’ totals as state — explodes the state space; the suffix-sum identity eliminates the need.

8. Skills & Takeaways

  • Game DP from current-player POV.
  • Suffix sums as zero-cost “rest of game” total.
  • Dynamic state parameter (M grows).

9. When to Move On

  • Solve cold in 35 min, articulate the suffix-sum identity unprompted.
  • Cap M correctly, handle the “take everything” base case.
  • Mention the Stone Game family.

10. Company Context

  • Google: L5/L6; classic game DP.
  • Amazon: L6; alternate-turn DP probe.
  • Meta: E5; less common.

Strong: “Game DP from current-player POV with suffix-sum identity; cold; capped M, handled base case, cited family.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
POVTries Alice-specificCurrent-player after hintCurrent-player cold+ cites identity proof
IdentityMissesAfter hintCold+ derives suf cancellation
M capMissesAfter testCold+ proves M ≤ n suffices
FamilyNoneNoneStone Game I/III+ minimax-on-DAG framing at Principal

12. Level Delta

  • Mid (L4): Minimax brute; gets memo after struggle.
  • Senior (L5): Game DP from current-player POV with suffix-sum identity, cold; correct M cap and base case.
  • Staff (L6): + cites Stone Game family + minimax-on-DAG framing.
  • Principal (L7+): + alpha-beta pruning + Nash equilibrium for non-zero-sum + connection to MDPs and policy iteration.

13. Follow-up Q&A

Q1: What if it’s Bob’s turn first? A1: Return total - dp[0][1] since dp gives current-player optimal.

Q2: 3 players? A2: Cyclic; dp[i][M][turn]; current player’s max but each tracks own. State doubles.

Q3: Non-zero-sum (e.g., bonuses)? A3: Suffix-sum identity breaks; need to track both totals as state (or as differences) — much larger.

Q4: Bob plays adversarially against Alice (not for Bob’s own max)? A4: Bob’s objective = minimize Alice. Still minimax but Bob’s dp[i][M] = min Alice’s future gain. Identity still works.

Q5: Reconstruct Alice’s actual moves? A5: At each state, record argmax x; replay from (0,1).

14. Solution Walkthrough

See solution.py:

  • stone_game_ii_dp — bottom-up O(n²) iterative.
  • stone_game_ii_memo — top-down @lru_cache.
  • stone_game_ii_brute — recursive minimax without memo (exponential oracle).

15. Beyond the Problem

Principal code review: “Stone Game II is the prototype for ‘minimax DP with dynamic parameter’. The suffix-sum identity (my_total = total - opponent_optimal) is the algebraic move that collapses a 2-quantity state into a 1-quantity state. The same move underlies: zero-sum 2-player games in game theory (‘Nash equilibrium reduces to 1-player optimization on a transformed payoff’), backpressure routing (‘queue differential collapses 2 queue states into 1 gradient’), and even gradient descent (‘only the relative loss matters; absolute level is free’). At Staff+, articulate this as: ‘when the game is zero-sum, the state collapses by one dimension via conservation.’ Then point out the next level: non-zero-sum requires Nash equilibrium computation (NP-hard in general; LP for 2-player zero-sum) — and that’s why this problem is solvable in polynomial time only because of the zero-sum structure.”