LeetCode 486 Predict the Winner - State Design

$dp[i][j]$ = the maximum score difference the current player can achieve on subarray nums$[i..j]$. Positive means current player wins on this subarray, negative means they lose. Base case: $dp[i][i] = \text{nums}[i]$. Only one element left. Current player takes it, and the difference equals that value since opponent gets nothing from this subarray.

This is interval DP: we compute answers for smaller ranges first, then build up to larger ranges. Process subarrays of length $1$, then $2$, then $3$, and so on. The final answer is $dp[0][n-1]$.