Game DP (minimax on a range)

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Piles of coins lie in a row: [1, 5, 2]. Two players take turns; on your turn you take the pile at either end. Both play as well as possible. Does the first player end with at least as many coins as the second?

By hand you would play it out. First player takes 1: the second player sees [5, 2] and takes 5, leaving 2 for the first, so the first has 3 and the second has 5. First player takes 2 instead: the second player sees [1, 5], takes 5, and the first ends with 1 + 2 = 3 against 5. Either way the first player loses. For three piles this is quick, but every move branches into two, so n piles means about 2ⁿ games to play out, and you have to assume the opponent always answers with their best reply, which is itself a full search.

Build the structure, one piece at a time

First, change what you keep score of. Instead of two totals, track one number: the difference, my coins minus yours, from the point of view of whoever is about to move. Taking a pile worth v adds v to my side, and then the opponent moves and will force some difference in their favour on what remains. So my best difference is v minus the opponent's best difference on the rest.

Second, notice that "the rest" is always a contiguous range of piles, from index i to j. So keep a table dp[i][j] = best difference the player to move can force on piles i..j. Fill it by range length, shortest first:

1. One pile: the mover takes it. dp[0][0] = 1, dp[1][1] = 5, dp[2][2] = 2.
2. Two piles [1, 5]: take 1 → 1 − dp[1][1] = 1 − 5 = −4; take 5 → 5 − dp[0][0] = 4. Best 4. Likewise dp[1][2] on [5, 2]: take 5 → 5 − 2 = 3; take 2 → 2 − 5 = −3. Best 3.
3. Three piles [1, 5, 2]: take 1 → 1 − dp[1][2] = 1 − 3 = −2; take 2 → 2 − dp[0][1] = 2 − 4 = −2. Best −2.

dp[0][2] = −2 is negative, so the first player cannot win, matching the by-hand play.

Why it is correct

The invariant: dp[i][j] is the largest lead the player to move can guarantee on that range, assuming the other player also plays to maximise their own lead. Two players maximising their own lead is the same as each minimising the other's, because the leads are negatives of each other. So after I take v, the opponent faces a smaller range and forces exactly dp of that range in their favour, which counts against me. Taking the better of the two ends therefore gives the true guaranteed lead, provided the smaller ranges are already correct, which the fill order ensures.

dp[i][j] = max( a_i − dp[i+1][j], a_j − dp[i][j−1] )

Why it is fast

There are about n²/2 ranges and each is settled with two subtractions and one comparison. That is O(n²) work: for 20 piles about 200 cells against roughly a million played-out games. The difference trick is what makes the table small; tracking both players' totals separately would need the totals in the state and blow it up.

How to recognise it in an interview

Cues: two players, alternate turns, both play optimally, "can the first player win" or "maximum score". Say: I will keep the score as a difference from the mover's point of view, so one table serves both players. Predict the Winner is this example. Stone Game is the same with an even number of piles. Stone Game III lets the mover take 1, 2 or 3 piles from one end, so the state is a single index and the maximum runs over three moves.

02The idea in one line

Score difference view: best = max over moves of (gain − opponent's best).

Reach for it when: Predict the winner, stone game I/II/III, can I win, flip game II.

Cost: O(n²) time.

03The walk-through, step by step

The video works one example: Predict the Winner on [1,5,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Think in score difference: my gain minus whatever the opponent then forces
2. One pile: the mover takes it, lead = its value
3. Fill by range length: pairs first, then the whole array
4. dp[0][1]: take 1 → 1−5 = -4; take 5 → 5−1 = 4; best 4
5. dp[1][2]: take 5 → 5−2 = 3; take 2 → 2−5 = -3; best 3
6. dp[0][2]: take 1 → 1−3 = -2; take 2 → 2−4 = -2; best -2
7. dp[0][2] = -2 < 0: player 1 cannot win on [1,5,2]
8. Every range once, two moves each: O(n²)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Digit DP, Counting ways with modulo, DP over sorted keys (chains).