I always like using backtrack programing instead of DP to intuitively solve a quesiton when it is about making choices. So clearly this question can be solved by backtrack going through every possible choices that 2 players can have. Let me elaborate my idea!

Let's denote the 1th player by A and denote the 2th player by B.

As the question shows, given nums[], we are trying to see **whether A always have a optimal strategy to win** or **B always have a optimal strategy to win/prevent A's win**, so let's just stand by A. Say after several runs A is the winner, then we must have SA - SB>=0, where SA is the sum of all A get and SB is the sum of all B get.

So now let's get started from the beginning, initially before A and B making choices, Total = SA - SB=0.

(1) Then A have two choices:

(A.1) **Pick nums[left] and set Total = Total + nums[left++]**, then go to (2) to see if this choice is optimal to guarantee A's win, if it is, we return **true** to indicate A as winner, else we go for A.2.

(A.2) **Pick nums[right] and set Total = Total + nums[right--]**, then go to (2) to see if this choice is optimal to guarantee A's win, if it is, we return **true** to indicate A as winner, else we return **false** to indicate B as winner/A as loser.

(2) Once A have made either choice above, B have two choices:

(B.1) **Pick nums[left] and set Total = Total - noms[left++]**, then go to (1) to see if this choice is optimal to guarantee B's win, if it is, we return **false** to indicate B as winner, else we go for B.2.

(B.2) **Pick nums[right] and set Total = Total - nums[right--]**, then go to (1) to see if this choice is optimal to guarantee B's win, if it is, we return **false** to indicate B as winner, else we return **true** to indicate A as winner/B as loser.

**Once left==right, we know that A and B have no choices**, then A win if Total>=0, else B win

```
public class Solution {
public boolean PredictTheWinner(int[] nums) {
return predictHelper(nums,0, 0,nums.length-1);
}
public boolean predictHelper(int[] nums, int total, int left, int right){
if(left==right){//A and B have no choices
if(total>=0) return true; //A's win
else return false; //B's win
}
else if(left<right){ //player A making choices
if(predictHelper(nums, total+nums[left++], right, left)|| //try A.1
predictHelper(nums, total+nums[right--], right, --left)) //backtrack to reset left pointer and try A.2
return true; //A.1 or A.2 can guarantee A's win
else return false; //A will always lose given the current strategy
}
else {//player B making choices
if(!predictHelper(nums, total-nums[right++], right, left)|| //try B.1
!predictHelper(nums, total-nums[left--], --right, left)) //backtrack to reset right pointer and try B.2
return false; //B.1 or B.2 can guarantee B's win
else return true; //B will always lose given the current strategy
}
}
}
```