Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 486 Predict the Winner - Key Idea

Score difference trick

Don't track two separate scores. Track the difference: dp[i][j]dp[i][j] = maximum (current player's score - opponent's score) for subarray [i,j][i, j].

Why difference? When I pick, I gain points. Then it's opponent's turn, and their "best difference" becomes my negative. The signs flip automatically. Player 11 wins if dp[0][n1]0dp[0][n-1] \geq 0: their advantage over the full array is non-negative. This single-number state avoids tracking both players' scores separately.