← DSA Atlas
Dedicated problem page · #486

Predict the Winner

MediumTwo-Dimensional Dynamic ProgrammingMinimax on interval score differenceInterval dynamic programming (game theory)
Solve on LeetCode ↗
486
MediumTwo-Dimensional Dynamic ProgrammingInterval dynamic programming (game theory)Minimax on interval score difference

Predict the Winner

Two players take turns picking a number from either the left or right end of the array nums, adding it to their score. Player 1 goes first. Assuming both play optimally to maximize their own score, return true if Player 1 can win (score at least as high as Player 2), otherwise false.

Open official problem prompt ↗
In plain English

Decide whether the first player can guarantee a non-losing score when both players pick greedily-optimally from the ends of the array.

Picture it like this

Two chess players sharing a scorecard where only the gap matters: each move you widen your own lead, but you know your opponent will then try just as hard to close it, so you plan for the net swing rather than raw points.

Example
Input
nums = [1, 5, 2]
Output
false
Why
Player 1 picks 2 (best end), then Player 2 picks 5, Player 1 gets 1: 3 vs 5, so Player 1 cannot win.
Constraints
1 <= nums.length <= 200 <= nums[i] <= 10^7
Pattern lesson

See the pattern, then code

Minimax on interval score difference
Recognition clue

Two players alternate, both play optimally, and choices are from the ends of a range; optimal play over sub-ranges is the hallmark of minimax interval DP.

↗
Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Track the score difference (current player minus opponent) rather than two separate scores. The current player picks an end, gains that value, then faces the opponent's best difference on the remaining range, which is subtracted because roles flip.

New words, made simpleKnow these before the algorithm
Minimax
A strategy where each player maximizes their own outcome assuming the opponent responds optimally against them.
Score difference
Encoding the game state as (my score minus opponent's) so a single number captures who is ahead.
Turn symmetry
Both players use the same optimal rule, so the opponent's best difference simply gets negated when it becomes your turn.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Recursion without memo

Exponential; recomputes the same ranges repeatedly.

Recurse on (i, j) choosing an end each turn.

Time O(2^n)Space O(n)
Two-score DP

Works but carries redundant state; only the difference matters.

Track both players' totals separately per range.

Time O(n^2)Space O(n^2)
Best choiceDifference interval DP

Cleanest correct formulation; single value per range and easy transition.

dp[i][j] stores the best current-minus-opponent difference on nums[i..j].

Time O(n^2)Space O(n^2)
The rule we keep true

Invariant

dp[i][j] is exactly the maximum score margin the player to move can secure over the opponent when only nums[i..j] remains.

Why this is correct

Reasoning

Whichever end the current player takes, the opponent then plays the same optimal strategy on the smaller range, achieving dp of that subrange for THEMSELVES; from the current player's view that is a deficit, hence the subtraction. Maximizing over the two ends yields the current player's best guaranteed margin, and a non-negative full-range margin means Player 1 does not lose.

The algorithm in three movesSay these aloud before coding
1Define dp[i][j] as the best achievable (current player minus opponent) score difference on nums[i..j]

dp[i][i] = nums[i]

2Base case: a single element gives difference nums[i]

dp[0][1] = max(1-5, 5-1) = 4

3For longer ranges, choose the left or right end: nums[i] - dp[i+1][j] or nums[j] - dp[i][j-1]

dp[0][2] = max(1-dp[1][2], 2-dp[0][1]) = max(1-3, 2-4) = -2

4Fill by increasing range length

5Player 1 wins iff dp[0][n-1] >= 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
51
22
1 · Readnums = [1,5,2]
2 · AskSingle-element ranges?
3 · Update statedp[0][0]=1, dp[1][1]=5, dp[2][2]=2
4 · ResultDiagonal filled
Key takeaway

Players may only remove from the two highlighted ends of the current range.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Base diagonal

    A range of one element gives that element as the margin for whoever moves.

  2. 2
    Lines 7-11Grow ranges

    For each length, the transition negates the opponent's best sub-range margin, capturing turn flips.

  3. 3
    Lines 12Verdict

    A non-negative full-range margin means Player 1 ties or wins.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element: Player 1 takes it and trivially wins (dp >= 0)
  • Ties count as a win for Player 1 because of the >= comparison
  • All-equal arrays give margin 0 on even length, still a win
!

Common beginner mistakes

  • Adding instead of subtracting the sub-range dp, forgetting the turn flips
  • Comparing to > 0 instead of >= 0 (a tie should return true)
  • Filling the table in row order instead of by increasing length, reading uncomputed cells
Check your understanding

Why does subtracting dp[i+1][j] correctly model the opponent's turn?

More in Two-Dimensional Dynamic Programming

#1143Longest Common SubsequenceSequence-alignment grid DP#72Edit DistanceSequence-alignment grid DP#10Regular Expression MatchingPattern-matching grid DP with star lookback#44Wildcard MatchingGlob-matching grid DP#62Unique PathsGrid path-counting DP#63Unique Paths IIGrid path-counting DP with obstacles