Predict the Winner

medium dp game theory recursion

Problem

Players take turns picking from either end of nums; both play optimally to maximise their score. Return true iff player 1 can win (tie counts as a win).

Inputnums = [1,5,2]

Outputfalse

dp[i][j] = max(nums[i] − dp[i+1][j], nums[j] − dp[i][j-1]); answer = dp[0][n-1] ≥ 0.

nums (length 2–6)

def predict_the_winner(nums):
    n = len(nums)
    dp = [row[:] for row in [[0]*n]*n]
    for i in range(n): dp[i][i] = nums[i]
    for L in range(2, n+1):
        for i in range(n-L+1):
            j = i + L - 1
            dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
    return dp[0][n-1] >= 0

function PredictTheWinner(nums) {
  const n = nums.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = nums[i];
  for (let L = 2; L <= n; L++)
    for (let i = 0; i + L <= n; i++) {
      const j = i + L - 1;
      dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
    }
  return dp[0][n-1] >= 0;
}

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = nums[i];
        for (int L = 2; L <= n; L++)
            for (int i = 0; i + L <= n; i++) {
                int j = i + L - 1;
                dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        return dp[0][n-1] >= 0;
    }
}

bool PredictTheWinner(vector& nums) {
    int n = nums.size();
    vector> dp(n, vector(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    for (int L = 2; L <= n; L++)
        for (int i = 0; i + L <= n; i++) {
            int j = i + L - 1;
            dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
        }
    return dp[0][n-1] >= 0;
}

Explanation

Instead of tracking both players' scores separately, the slick idea is to track the score difference from the point of view of whoever is about to move. dp[i][j] is the best lead the current player can secure over the opponent on the subarray nums[i..j].

Whoever moves can take either end. If they take nums[i], they gain that value but then become the opponent on nums[i+1..j], where the other player builds their own lead dp[i+1][j] against them. So this choice is worth nums[i] - dp[i+1][j]. Taking the right end is similarly nums[j] - dp[i][j-1]. The player picks the bigger of the two.

The base case is a single element: dp[i][i] = nums[i], since the only move is to grab it. We then fill larger ranges by length so the smaller subarrays they depend on are ready.

At the end, dp[0][n-1] is player 1's net lead over the whole array. Player 1 wins (or ties) exactly when this is >= 0.

Example: nums = [1, 5, 2]. Working it out, player 1's best net lead is negative, so the function returns false — player 1 cannot guarantee a win.

Time: O(n²) Space: O(n²)