## Algorithm

Problem Name: 486. Predict the Winner

You are given an integer array `nums`. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of `0`. At each turn, the player takes one of the numbers from either end of the array (i.e., `nums[0]` or `nums[nums.length - 1]`) which reduces the size of the array by `1`. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return `true` if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return `true`. You may assume that both players are playing optimally.

Example 1:

```Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return false.
```

Example 2:

```Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
```

Constraints:

• `1 <= nums.length <= 20`
• `0 <= nums[i] <= 107`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define MAX_LEN 20
#define IDX(S, E) ((S) * (MAX_LEN) + (E))

typedef struct {
bool flag;
int val;
} m_t;

int _max(int a, int b) {
if (a > b) return a;
return b;
}

int helper(int *nums, int s, int e, m_t *mem) {
int a, b, c;
m_t *m;

if (s == e) {
c = nums[s];
} else {
a = nums[s];    // pick the first one
m = &mem[IDX(s + 1, e)];    // the rest
if (m->flag) {
a -= m->val;
} else {
a -= helper(nums, s + 1, e, mem);
}

b = nums[e];    // pick the last one
m = &mem[IDX(s, e - 1)];    // the rest
if (m->flag) {
b -= m->val;
} else {
b -= helper(nums, s, e - 1, mem);
}
c = _max(a, b);
}

// save it
m = &mem[IDX(s, e)];
m->flag = 1;
m->val = c;

return c;
}

bool PredictTheWinner(int* nums, int numsSize){
m_t mem[MAX_LEN * MAX_LEN] = { 0 };
if (helper(nums, 0, numsSize - 1, mem) >= 0) return true;
return false;
}
``````
Copy The Code &

Input

cmd
nums = [1,5,2]

Output

cmd
false

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool PredictTheWinner(vector& nums) {
vectorscore(2);
return solve(nums, score, 0, 0, nums.size() - 1);
}

bool solve(vector& nums, vector& score, int player, int l, int r) {
if (l >= r) {
return score[0] >= score[1];
}

if (player == 0) {
// Pick left
score[0] += nums[l];
if (solve(nums, score, player ^ 1, l + 1, r)) {
score[0] -= nums[l];
return true;
}
score[0] -= nums[l];
// Pick right
score[0] += nums[r];
if (solve(nums, score, player ^ 1, l, r - 1)) {
score[0] -= nums[r];
return true;
}
score[0] -= nums[r];
} else {
// Pick left
score[1] += nums[l];
if (!solve(nums, score, player ^ 1, l + 1, r)) {
score[1] -= nums[l];
return false;
}
score[1] -= nums[l];
// Pick right
score[1] += nums[r];
if (!solve(nums, score, player ^ 1, l, r - 1)) {
score[1] -= nums[r];
return false;
}
score[1] -= nums[r];
}
return player;
}
};
``````
Copy The Code &

Input

cmd
nums = [1,5,2]

Output

cmd
false

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const PredictTheWinner = function(nums) {
// The dp[i][j] saves how much more scores that the first-in-action player will get from i to j than the second player.
const dp = [];
for (let i = 0; i <= nums.length; i++) {
dp.push(Array(nums.length).fill(0));
}
for (let s = nums.length - 1; s >= 0; s--) {
dp[s][s] = nums[s];
for (let e = s + 1; e < nums.length; e++) {
let a = nums[s] - dp[s + 1][e];
let b = nums[e] - dp[s][e - 1];
dp[s][e] = Math.max(a, b);
}
}
return dp[0][nums.length - 1] >= 0;
};

console.log(PredictTheWinner([1, 5, 233, 7]));
console.log(PredictTheWinner([3, 5, 3]));
``````
Copy The Code &

Input

cmd
nums = [1,5,233,7]

Output

cmd
true

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def PredictTheWinner(self, nums):
def dfs(l, r, p1, p2, turn):
if l > r:
return p1 >= p2
elif turn:
return dfs(l + 1, r, p1 + nums[l], p2, 0) or dfs(l, r - 1, p1 + nums[r], p2, 0)
else:
return dfs(l + 1, r, p1, p2 + nums[l], 1) and dfs(l, r - 1, p1, p2 + nums[r], 1)
return dfs(0, len(nums) - 1, 0, 0, 1)
``````
Copy The Code &

Input

cmd
nums = [1,5,233,7]

Output

cmd
true