This is a zero-sum two-player game, and the classic tool for it is a minimax difference DP. Instead of tracking two separate scores, define dp[l][r] as the largest margin the player whose turn it is can force from the subarray nums[l..r] — their score minus their opponent’s. If that margin comes out non-negative, Player 1 wins; literally return dp[0][n-1] >= 0. The magic is that the margin does all the work: when you take an end, the other player now owns the remaining subarray, so your resulting margin is nums[end] - dp[remaining] — you flip the sign of the child, then your opponent’s best play is already encoded in that child, and optimal play is just picking the larger of the two flipped outcomes.
Brute Force: Recursive Minimax
Time O(2^n)Space O(n)Model the game directly. dfs(l, r) returns the margin the mover can force from nums[l..r]. If the range is empty, the mover adds nothing, so the margin is 0. Otherwise they compare the two ends: take nums[l], and the opponent then owns nums[l+1..r], so the resulting margin is nums[l] - dfs(l + 1, r); or take nums[r] for a margin of nums[r] - dfs(l, r - 1). Optimal play picks whichever end gives the larger margin, so dfs returns the max of the two. This exactly mirrors the minimax idea, with no memoization.
class Solution: def predictTheWinner(self, nums: list[int]) -> bool: def dfs(l: int, r: int) -> int: if l > r: return 0 return max(nums[l] - dfs(l + 1, r), nums[r] - dfs(l, r - 1)) return dfs(0, len(nums) - 1) >= 0Why it is exponential: each call branches into two, so the recursion tree doubles per step. Every distinct (l, r) pair is reached by many different pick histories — the same subproblem is solved over and over, giving O(2^n) time. The recursion depth is O(n), paid on the call stack.
Interval DP
OptimalTime O(n²)Space O(n²)The brute force recomputes the same intervals repeatedly. Turn dfs into a table: dp[l][r] holds the same value as dfs(l, r). Seed the diagonal — a length-1 interval has only one move, so dp[i][i] = nums[i]. Then fill intervals by increasing length: for each dp[l][r], its two children (dp[l+1][r] and dp[l][r-1]) were both solved in the previous, shorter length, so the transition dp[l][r] = max(nums[l] - dp[l+1][r], nums[r] - dp[l][r-1]) is always computable. The answer is dp[0][n-1] >= 0.
class Solution: def predictTheWinner(self, nums: list[int]) -> bool: n = len(nums) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = nums[i] for length in range(2, n + 1): for l in range(n - length + 1): r = l + length - 1 dp[l][r] = max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]) return dp[0][n - 1] >= 0Trace example 1, nums = [1,5,2] — watch the diagonal seed, then each longer interval reading its two already-solved children, ending with a negative margin in the top-right corner:
Array — take either end
dp[l][r] — biggest margin the mover can force
each dp[l][r] = max( nums[l] − dp[l+1][r], nums[r] − dp[l][r−1] ) — the two amber children are the subarrays left after taking each end
nums = [1,5,2] returns false. 1,5,2 is the whole array. Two players take turns pulling a number from either END of the remaining array, adding it to their own score. dp[l][r] is the biggest margin the player to move can force from the subarray nums[l..r] — by how much they can come out ahead of their opponent. Since it is a zero-sum difference, if it ends non-negative, Player 1 wins; we fill the table length by length and read the answer from the top-right corner.
Then example 2, nums = [1,5,233,7] — a length-4 interval collapsed into two length-3 choices, proving Player 1’s first pick of the 1 forces their win:
Array — take either end
dp[l][r] — biggest margin the mover can force
each dp[l][r] = max( nums[l] − dp[l+1][r], nums[r] − dp[l][r−1] ) — the two amber children are the subarrays left after taking each end
nums = [1,5,233,7] returns true. 1,5,233,7 is the whole array. Two players take turns pulling a number from either END of the remaining array, adding it to their own score. dp[l][r] is the biggest margin the player to move can force from the subarray nums[l..r] — by how much they can come out ahead of their opponent. Since it is a zero-sum difference, if it ends non-negative, Player 1 wins; we fill the table length by length and read the answer from the top-right corner.
Why it is quadratic: there are O(n²) intervals, and each is solved in O(1) from its two children, so time is O(n²). The triangular table holds O(n²) values. A balance — the sum dp[l+1][r] + dp[l][r-1] — lets you drop space to O(n), but O(n²) is the 2-D DP standard and the difference never matters at n ≤ 20.