Predict the Winner
You are given an integer array nums. Players 1 and 2 take turns, with Player 1 starting first.
On each turn, a player removes either the first or the last element from the array and adds it to their score. The game ends when the array is empty.
Assuming both players play optimally, return true if Player 1 can win (score >= Player 2's score), otherwise return false.
Examples
Input: [1,5,2]
Output: false
Input: [1,5,233,7]
Output: true
Hints
Use interval DP. Define `dp[l][r]` as the maximum score difference the current player can achieve from subarray `nums[l..r]`.
The recurrence is `dp[l][r] = max(nums[l] - dp[l+1][r], nums[r] - dp[l][r-1])`. The current player picks one end and subtracts the opponent's optimal advantage from the remaining subarray.
Return `dp[0][n-1] >= 0` to check if Player 1's score is at least Player 2's.
Related Problems
Predict the Winner
You are given an integer array `nums`. Players 1 and 2 take turns, with Player 1 starting first.