Hard Problemsoptimizationinterval

Optimal Strategy for a Game

Coins of varying values sit in a row. Two players alternate turns, each turn taking either end coin of the remaining row, and both play to maximize their own total. Find the maximum total the first player can guarantee regardless of how the second player plays.

Do this lesson first: house robber

Example input

coins = [8, 15, 3, 7]

Expected output

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is the most the player ABOUT TO MOVE can collect from coins i..j, both ends included, when those are the only coins left and both players play their best from there. It is not tied to the first player: whoever is on move faces exactly this question about exactly this stretch, so one table serves both of you. Two numbers name the state, where the remaining row starts and where it ends, so only the upper triangle, i <= j, means anything, and the answer, the first player moving on the whole row, sits in the top-right corner at dp[0][n - 1].

dp[i][j] = max(S - dp[i + 1][j], S - dp[i][j - 1]), where S = coins[i] + ... + coins[j]; dp[i][i] = coins[i]

Your move is one of two things: take the left coin or take the right coin. Two options, keep the better one: the max over two choices that the house robber lesson derives at /courses/dynamic-programming/house-robber, rob this house or skip it. What is new here is what happens after you choose. You take an end, and your opponent is now the player about to move on the stretch that is left, and they play it as well as you would, so they collect exactly dp of that stretch, the quantity this table stores. Every coin on the stretch ends up with one of you, so you get everything they do not: S - dp[i + 1][j] if you took the left coin, S - dp[i][j - 1] if you took the right. The coin you took is inside S, which is why it never appears on its own. Notice where the opponent's play went: you never write a min over their replies, because their best total on the rest is already your worst case, and subtracting it from S states that directly.

dp[i][i] = coins[i] on the diagonal: with one coin left, the player to move takes it and the game ends. Every other cell reads exactly two cells, each one coin shorter: dp[i + 1][j], the stretch without its left coin, directly below, and dp[i][j - 1], the stretch without its right coin, directly to the left. S is added up from the coins themselves, not read from the table. Filling by length, every pair of coins, then every run of three, and so on, has both reads final before the cell needs them, which on the grid is a sweep along the diagonals out to the top-right corner.

Tabulation over n(n + 1) / 2 stretches. With S taken as a difference of prefix sums, each cell is constant work, so O(n²) time and O(n²) space; at 4 coins that is 10 cells, 4 bases and 6 computes, each choosing between two ends. A cell reads only its own row and the row below, so running i down from n - 1 with j rising needs just two rows, O(n) space. Top-down memoization from dp[0][n - 1] saves nothing: any stretch i..j is reachable by taking i coins off the left and n - 1 - j off the right, and measured at every slider size it visits all n(n + 1) / 2 of them.

Time O(n²)Space O(n²), reducible to O(n)

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Rows ↓
Cols →

0: 8

1: 15

2: 3

3: 7

0: 8

1: 15

2: 3

3: 7

Rows ↓row i: the first coin still on the table

Cols →column j: the last coin still on the table, so the cell is the most the player to move collects from coins i..j

optimal-strategy-for-a-game.ts

1function firstPlayerTotal(coins) {
2 const n = coins.length;
3 const pre = [0];
4 for (const c of coins) pre.push(pre[pre.length - 1] + c);
5 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
6 for (let i = 0; i < n; i++) dp[i][i] = coins[i];
7 for (let len = 2; len <= n; len++) {
8 for (let i = 0; i + len - 1 < n; i++) {
9 const j = i + len - 1;
10 const sum = pre[j + 1] - pre[i];
11 dp[i][j] = Math.max(sum - dp[i + 1][j], sum - dp[i][j - 1]);
12 }
13 }
14 return dp[0][n - 1];
15}

Base caseComputedBeing readAnswer

The code, the trap, the variations

optimal-strategy-for-a-game.ts

1function firstPlayerTotal(coins) {
2 const n = coins.length;
3 const pre = [0];
4 for (const c of coins) pre.push(pre[pre.length - 1] + c);
5 const dp = Array.from({ length: n }, () => new Array(n).fill(0));
6 for (let i = 0; i < n; i++) dp[i][i] = coins[i];
7 for (let len = 2; len <= n; len++) {
8 for (let i = 0; i + len - 1 < n; i++) {
9 const j = i + len - 1;
10 const sum = pre[j + 1] - pre[i];
11 dp[i][j] = Math.max(sum - dp[i + 1][j], sum - dp[i][j - 1]);
12 }
13 }
14 return dp[0][n - 1];
15}

Where people go wrong

Taking the larger end coin every turn. It feels safe, a bigger coin now is a bigger coin, and on this page's coins it is right at 2, 3, 5 and 7 coins. At 4 it fails at once: on 8, 15, 3, 7 it takes the 8, because 8 beats 7, and that hands the 15 to your opponent; you finish with 8 + 7 = 15, where taking the 7 first guarantees 22. Played against an opponent who answers well, greedy also falls short at 6, 8 and 9 coins: 21 against 24, 25 against 30, 27 against 34. The coin you take matters less than the coin you expose. The other common slip forgets the opponent altogether: dp[i][j] = max(coins[i] + dp[i + 1][j], coins[j] + dp[i][j - 1]) treats the rest of the row as yours too, so every cell comes out as the sum of its coins, 33 at 4 coins, as if you were playing alone.

Store the margin instead of the total: how far ahead the player to move finishes.
diff[i][j] = max(coins[i] - diff[i + 1][j], coins[j] - diff[i][j - 1]), with diff[i][i] = coins[i]. The coin you take counts for you and the opponent's best margin on the rest counts against you, so no sum is needed. The triangle, the two reads and the fill by length do not change. The first player's total comes back as (S + diff) / 2: at 4 coins the margin is 11 and (33 + 11) / 2 = 22. When the question is only whether the first player can at least tie, that is the margin being 0 or more.
Look two moves ahead instead of subtracting from S.
The textbook form: dp[i][j] = max(coins[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), coins[j] + min(dp[i + 1][j - 1], dp[i][j - 2])). You take an end, the opponent takes whichever end leaves you less, and you move again on what is left. It reads three cells two coins shorter, and an empty stretch has to count as 0. The state and the answers do not change: it gives the same total at every slider size. It just spells out the opponent's reply that S - dp[...] keeps folded away.
With an even number of coins, only guarantee at least half.
No table is needed. Number the coins from 0: the first player can take every even-numbered coin, or every odd-numbered one, because after each of your moves both ends left to the opponent have the other parity. So you can always collect the larger of the two parity sums, which is at least half. That is a guarantee, not the optimum: on 5, 3, 7, 10 the parity sums are 12 and 13, while the table finds 15, starting by taking the 10.
Return the moves, not just the total.
The table is unchanged; replay the game against it. On a stretch i..j, the mover takes the left coin if S - dp[i + 1][j] is at least S - dp[i][j - 1], otherwise the right one, and the stretch shrinks. At 4 coins the line is: you take the 7, the opponent takes the 8, you take the 15, the opponent takes the 3. The opponent's move is a tie on that table, dp[0][2]'s two ends are worth 11 each, so they could take the 3 instead and you still collect the 15.

Word Wrap Problem The painter's partition problem