Problem Description

The "Predict the Winner" problem is a classic game theory problem where two players (Player 1 and Player 2) take turns picking numbers from either end of an array. Both players play optimally to maximize their own score. The goal is to determine if Player 1 can win or tie.

Rules:

• Players alternate turns, with Player 1 going first
• On each turn, a player must pick from either the left or right end of the array
• Both players play optimally (always make the best possible move)
• Player 1 wins if their final score ≥ Player 2's score

Example: [1, 5, 2]

• Player 1 takes 2, Player 2 takes 5, Player 1 takes 1
• Final scores: Player 1 = 3, Player 2 = 5
• Player 1 loses, so return false

Algorithm Walkthrough

This solution uses dynamic programming with a key insight: instead of tracking both players' scores separately, we track the score difference from the current player's perspective.

Core Concept

dp[i][j] represents the maximum score advantage the current player can achieve over their opponent when playing optimally on the subarray from index i to j.

DP State Transition

For subarray [i, j], the current player can either:

1. Pick left element (nums[i]): Gain nums[i] points, then opponent plays optimally on [i+1, j]
2. Pick right element (nums[j]): Gain nums[j] points, then opponent plays optimally on [i, j-1]

The recurrence relation:

dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])

Why subtract dp[i+1][j]?

• Current player gains nums[i]
• Opponent then plays optimally on remaining subarray, gaining dp[i+1][j] advantage
• Net advantage for current player: nums[i] - dp[i+1][j]

Building the Solution

1. Base case: dp[i][i] = nums[i] (single element, no opponent)
2. Fill table: Build up from smaller subarrays to larger ones
3. Final answer: dp[0][n-1] >= 0 means Player 1 can win/tie

Example Trace

For [1, 5, 2]:

• dp[0][0] = 1, dp[1][1] = 5, dp[2][2] = 2
• dp[0][1] = max(1-5, 5-1) = max(-4, 4) = 4
• dp[1][2] = max(5-2, 2-5) = max(3, -3) = 3
• dp[0][2] = max(1-3, 2-4) = max(-2, -2) = -2
• Result: -2 < 0, so Player 1 cannot win

Complexity Analysis

Time Complexity: O(n²)

• Outer loop: Iterates through all possible lengths (1 to n-1)
• Inner loop: For each length, iterates through all valid starting positions
• Total iterations: Approximately n²/2 subproblems
• Each iteration: O(1) work

Space Complexity: O(n²)

• 2D DP table: dp[n][n] stores results for all subarrays
• Optimization possible: Can reduce to O(n) space using 1D array since we only need previous row

Full Solution(Java)

The solution demonstrates the power of dynamic programming in game theory problems. The key insight is transforming a two-player optimization problem into a single-player problem by tracking score differences rather than absolute scores. This elegant approach reduces the complexity while maintaining optimal play for both players.

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 len = 1; len < n; len++) {
            for (int i = 0; i < n - len; i++) {
                int j = i + len;
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
}