#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/game-theory-dp/predict-the-winner-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/game-theory-dp/predict-the-winner-implementation

Repovive

LeetCode 486 Predict the Winner - Implementation - Game Theory DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 486 Predict the Winner - Implementation

The code

Here's the full solution:

function predictTheWinner(nums)
    n := length of nums
    dp := 2D (two-dimensional) array of size n × n
    // Base case: single elements
    for i := 0 to n - 1
        dp[i][i] := nums[i]
    // Fill for increasing lengths
    for length := 2 to n
        for i := 0 to n - length
            j := i + length - 1
            takeLeft := nums[i] - dp[i + 1][j]
            takeRight := nums[j] - dp[i][j - 1]
            dp[i][j] := max(takeLeft, takeRight)
    return dp[0][n - 1] >= 0

The outer loop iterates by subarray length. Each length, we try all starting positions $i$ , compute the ending position $j = i + \text{length} - 1$ , and fill $dp[i][j]$ using already-computed smaller subarrays. This keeps dependencies are satisfied.

Time: $O(n^2)$ . Space: $O(n^2)$ .