Predict the Winner
Medium · Dynamic Programming · Array · Math · Dynamic Programming · Recursion · Game Theory
Problem
You are given an integer array nums. Two players take turns, player 1 first. On a turn, a player removes the number at either end of the array and adds it to their score. The game ends when the array is empty.
Both players play as well as possible. Return true if player 1 finishes with a score greater than or equal to player 2's (a tie counts as a win for player 1), and false otherwise.
Examples
Input: nums = [2,9,3] Output: false
Whichever end player 1 takes, player 2 takes the 9 and wins 9 to 5.
Input: nums = [4,9,3,2] Output: true
Player 1 takes 2; whichever end player 2 takes, player 1 can then take the 9 and finish with 11 against 7.
Input: nums = [7] Output: true
Player 1 takes the only number.
Constraints
- 1 <= len(nums) <= 20
- 0 <= nums[i] <= 10^7
Approaches
- Play out every game — time O(2^n), space O(n)
Follow-up
With an even number of values, player 1 can always take every even-indexed value or every odd-indexed one, so player 1 never loses; the DP is needed for odd lengths. The use cases return the margin itself and change the moves to "one or two from the front".
Related problems
Start free on Cariara · Coding problems · System design studio
