Minimax DP — Optimal Play in Two-Player Games

Every two-player zero-sum game boils down to one question: "If I make this move, what's the best my opponent can do in response?"

This is the core insight that connects all 6 problems in this article. Whether you're picking stones from ends, guessing a number, or choosing integers from a set — the framework is identical:

1. Define the state — what does the current player need to know? (subarray i..j, range [i,j], bitmask of used numbers)
2. List the choices — what actions can the current player take? (pick left/right, pick pivot k, pick number n)
3. Evaluate opponent's best response — after each choice, what's the opponent's optimal result from the new state?
4. Pick the maximum — I choose the action that maximizes my final outcome, assuming my opponent plays optimally.

The key formula that appears in every minimax DP:

Let's see how this plays out across 6 classic problems, ordered by increasing complexity:

Problem: Given an integer array nums, two players pick from either end. Each picks the number and adds it to their score. The player with the higher score wins. Return true if the first player can win.

🔍 Real-Time Thinking — Aditya Verma Framework

"I'm at subarray i..j. I have two choices: pick nums[i] (left) or nums[j] (right). After I pick, my opponent faces a smaller subarray and plays optimally. My net advantage is what I take minus what my opponent gets from the remainder."

🤔 The Choose/Not-Choice Pattern

At every subarray, I make a decision: do I pick the left element or the right element? This is the classic choose/not-choose pattern:

• Choose left: I take nums[i] now. The opponent gets the best possible result from nums[i+1..j]. My net = nums[i] - opponent's best.
• Choose right: I take nums[j] now. The opponent gets the best possible result from nums[i..j-1]. My net = nums[j] - opponent's best.
• Decision: Pick the one that gives me the higher net advantage.

📋 Edge Cases to Consider

• Single element: dp[i][i] = nums[i]. First player takes it. Win if nums[i] ≥ 0 (or > 0 depending on problem variant).
• Two elements: dp[i][i+1] = max(nums[i] - nums[i+1], nums[i+1] - nums[i]) = |nums[i] - nums[i+1]|. The first player picks the larger one.
• Even length array: The first player can force a win by controlling which elements they access (they can pick all odd-indexed or all even-indexed elements by choosing the appropriate end).
• Zero scores: If all numbers are zero, dp[0][n-1] = 0. First player ties, not wins.
• Negative numbers: The recurrence works with negatives. dp tracks net advantage, so negative values are fine.

Problem: I'm guessing a number between 1 and n. Each time I guess wrong, I pay that amount. I need a strategy that minimizes the maximumamount I might have to pay (the "worst-case" cost).

🔍 Real-Time Thinking — Minimax on Decision Trees

"I pick a pivot k in [i, j]. If I guess k and it's wrong, I pay k and continue. The number is either lower (i..k-1) or higher (k+1..j). Since I want a guarantee, I prepare for the worst case — I take the max of the two branches. But I can choose the pivot k that minimizes this worst-case cost."

This is minimax in its purest form:

• Min — I choose the pivot that minimizes my worst-case total cost
• Max — For each pivot, the worst case is the higher-cost branch (lower or higher)

The Choose/Not-Choose Pattern Here

This problem has a different flavor of choose/not-choose:

• Choose pivot k: I decide which number to guess first. This determines the worst-case cost.
• Not-choose is implicit: Every other number in the range is a potential pivot I'm testing.
• But wait — this is really "choose the best pivot": I test ALL pivots and pick the one that MINIMIZES the worst-case cost.

📋 Edge Cases to Consider

• n = 1: dp[1][1] = 0. No wrong guesses needed. Only one possible number.
• n = 2: Guess 1 first. If wrong (number is 2), pay 1 and guess 2 (correct). Total = 1. Guess 2 first: pay 2. So dp = 1.
• n = 3: Best pivot is 2. dp = 2 + max(dp[1][1], dp[3][3]) = 2 + 0 = 2. If you guess 1: 1 + max(0, dp[2][3]) = 1 + 2 = 3. If you guess 3: 3 + max(dp[1][2], 0) = 3 + 1 = 4.
• Large n: The optimal pivot tends toward the middle, but not always exactly — the exact value depends on the cost asymmetry.

Optimal Strategy for a Game (GFG)

Problem: Same as Predict the Winner — pick from ends, maximize your total sum. Compute the maximum sum the first player can collect.

The difference from Predict the Winner: instead of computing net advantage (which could be negative), this problem asks for the actual maximum sum the first player can guarantee. The recurrence adapts slightly:

Sum Game

Problem: A variant where the two players alternately pick elements from the ends. The goal is to maximize the sum difference (like Predict the Winner). Some versions add constraints on when you can pick (e.g., only if the sum of remaining is odd/even).

The unified framework for ALL interval-pick-from-ends games:

Problem: Two players take turns picking numbers from 1 to maxChoosableInteger. Each number can be used at most once. The player who makes the cumulative sum reach or exceed desiredTotal wins. Can the first player force a win?

🔍 Real-Time Thinking — Choose/Not-Choose with Bitmask

"I have a set of available numbers. I pick one. If my cumulative score reaches the target, I win. Otherwise, it's my opponent's turn with a smaller set. I need to know: is there ANY number I can pick that makes my opponent lose? If yes, I win."

The state is a bitmask: an integer where bit i is 1 if number (i+1) has been used. This is the choose/not-choose pattern applied to picking from a set (not from ends):

• Choose number n: Mark it as used (set bit n-1 in mask). Add n to cumulative score.
• Not-choose: Every other available number is a potential choice I'm evaluating.
• Decision: If ANY choice makes opponent lose, I win from this state.

Choose/Not-Choose with Bitmask

This is where the choose/not-choose framework meets bitmask DP:

• State = bitmask: 2ⁿ states where n = maxChoosableInteger. Each bit tells us if a number is used.
• Choice = pick an unused number: For each 0-bit, we can set it to 1 and recurse.
• Minimax check: "If I pick number i and the opponent can't force a win from the new state — I win."
• Memoization: dp[mask] stores whether the current player can force a win from this state.

📋 Edge Cases to Consider

• desiredTotal ≤ 0: First player wins immediately without making any move.
• Sum of all numbers < desiredTotal: Nobody can reach the target. First player loses.
• maxChoosableInteger ≥ desiredTotal: First player can pick desiredTotal directly and win in one move.
• Large maxChoosableInteger (n > 20): 2ⁿ states may be too large. But usually the problem constraints keep it manageable (n ≤ 20).
• Even/odd parity: If all numbers can be paired to reach the target, the second player might have a mirroring strategy. Typical for desiredTotal = (maxChoosableInteger * (maxChoosableInteger + 1) / 2) where the player who goes second can mirror.

Problem: You start with 0 points. You draw numbers from [1, maxPts] with equal probability until your score reaches or exceeds K. If your final score ≤ N, you win. What's the probability of winning?

🔍 Real-Time Thinking — Probability DP

"I'm at score x. I can draw any number from 1 to maxPts. Each has probability 1/maxPts. After drawing, my new score is x + i. If x + i ≥ K, I stop. I win if x + i ≤ N. If not, I continue drawing."

The Choose/Not-Choose Pattern Here

New 21 Game has a different flavor of minimax — it's probability DP with optimal stopping:

• Choose to draw: Must draw if score < K. The draw is random (1..maxPts), each equally likely.
• Stop (not-choose): Once score ≥ K, you stop automatically and check if score ≤ N.
• The "minimax" here is against nature: The opponent is randomness, not another player. We compute expected probability, not worst-case.

📋 Edge Cases to Consider

• K = 0: Already stopped before starting. If 0 ≤ N, probability = 1.
• N ≥ K + maxPts - 1: You can always reach K without exceeding N. Maximum possible score is K + maxPts - 1. If N ≥ that, you always win.
• K = 1: You stop after exactly one draw. Probability = min(N, maxPts) / maxPts.
• N < K: You can never win because you must reach ≥ K to stop, but that means score > N.
• Large maxPts: The DP is O(n) regardless of maxPts thanks to sliding window.

1. Minimax = "I maximize, opponent minimizes" — always assume optimal play from both sides.
2. Aditya Verma's choose/not-choose: "At each number, I either pick it (score += num) or skip it — my opponent plays optimally after me. So I maximize(current + min(opponent's options))."
3. "Pick from ends" → interval DP — dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). This covers Predict the Winner, Optimal Strategy, Stone Game I, Sum Game.
4. "Guess to minimize worst-case" → decision tree DP — dp[i][j] = min over k of (k + max(dp[i][k-1], dp[k+1][j])). Used in Guess Number Higher Lower II.
5. "Pick from set, each once" → bitmask DP — dp[mask] = exists unused number i such that !dp[mask | (1 << i)]. Used in Can I Win.
6. "Stop when reaching threshold" → probability DP — dp[i] = sum(dp[i-w]...dp[i-1]) / maxPts with sliding window. Used in New 21 Game.
7. Winning state: exists a move to a losing state for opponent.
8. Losing state: all moves lead to winning states for opponent.
9. Time: O(n²) for interval DP, O(2ⁿ × n) for bitmask DP, O(n) for probability DP with sliding window.
10. Practice! — The only way minimax becomes intuitive is by solving problems. The 6 problems here are your training ground 🥋