hardDynamic Programming 2DPure DSA~35 min
Can the First Player Force a Win Taking From Either End
Two players alternately take a value from either end of a row of scores, each playing optimally to maximize their own total. Determine whether the first player can guarantee at least a tie.
Problem
Given an integer array nums, two players take turns picking a number from either end, adding it to their score. Both play optimally. Return true if player 1 can end with a score >= player 2's, else false.
Input
An integer array nums.
Output
A boolean: whether player 1 is guaranteed not to lose.
Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 10^7
- Both players play optimally.
Examples
Example 1
Input
nums = [1,5,2]
Output
false
Player 1 cannot guarantee a non-losing result against optimal play.
Example 2
Input
nums = [1,5,233,7]
Output
true
Player 1 can secure 234 versus 12.