Predict the Winner
Medium · 1-D Dynamic Programming · Explanation and code example
Interval DP for Score Difference
How it works
Track the best score difference the current player can guarantee on an interval. Choosing an end value gains that value, but the opponent then owns the best difference on the remaining interval, so subtract it. A nonnegative final difference means the first player can win or tie.
Steps
- Initialize one-value interval differences to their value.
- For increasing interval lengths, take max(left - inner-left, right - inner-right).
- Accept when the whole-interval difference is at least zero.
Complexity
- Time: O(n²).
- Space: O(n²).
Things to watch for
- Ties count as success for the first player.
- The DP stores a score difference, rather than a raw score.
- Subtract the opponent’s result after each choice.
Python code example
class Solution:
def predictTheWinner(self, nums: list[int]) -> bool:
n = len(nums)
dp = [[0] * n for _ in range(n)]
for i, value in enumerate(nums):
dp[i][i] = value
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
return dp[0][n - 1] >= 0
C++ code example
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
const int n = nums.size();
// dp[i][j] := the maximum number you can get more than your opponent in
// nums[i..j]
vector<vector<int>> dp(n, vector<int>(n));
for (int i = 0; i < n; ++i)
dp[i][i] = nums[i];
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
return dp[0][n - 1] >= 0;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.