787. Predict the Winner (Game Theory Recursion)

Two players take turns picking a number from either end of an array nums. Player 1 goes first. Both play optimally to maximize their own score. Return true if Player 1 can win or tie (score >= Player 2's), else false. Implement with recursion + memoization.

Input: An integer array nums.

Output: Return a boolean: true or false.

Examples

Input: [1,5,2]
Output: false
Explanation: Player 1 picks 1 or 2; Player 2 gets 5 either way -> Player 2 wins.

Input: [1,5,233,7]
Output: true
Explanation: Player 1 can achieve >= Player 2.

Input: [1]
Output: true
Explanation: Single element -> Player 1 takes it.

Constraints

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 10^7

Asked by