https://leetcode.com/problems/predict-the-winner/

X. DP

https://discuss.leetcode.com/topic/76830/java-9-lines-dp-solution-easy-to-understand-with-

improvement-to-o-n-space-complexity

https://discuss.leetcode.com/topic/76312/java-1-line-recursion-solution

X.

https://discuss.leetcode.com/topic/76319/java-dp-solution-with-explanation

https://discuss.leetcode.com/topic/76669/java-dp-solution-with-explanation

http://bookshadow.com/weblog/2017/01/22/leetcode-predict-the-winner/

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

Input: [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: [1, 5, 233, 7] Output: True Explanation: Player 1 first chooses 1. Then player 2 have 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.

Note:

- 1 <= length of the array <= 20.
- Any scores in the given array are non-negative integers and will not exceed 10,000,000.
- If the scores of both players are equal, then player 1 is still the winner.

X. DP

https://discuss.leetcode.com/topic/76830/java-9-lines-dp-solution-easy-to-understand-with-

improvement-to-o-n-space-complexity

The goal is maximize the sum of first player.

We have a numeric array from

`0 ~ n`

, `i`

and `j`

is the index. `dp[i][j]`

means the max sum we can get if the array starts from `i`

and ends to `j`

.
So

`dp[i][i]`

means only one coin and we pick firstly, `dp[i][i+1]`

means there are two coins, we pick the larger one.
To maximum our gain,

`dp[i][j] = max( nums[i] + dp[i + 1][j], dp[i][j - 1] + nums[j])`

, since we either will pick the `i`

or `j`

coin. But here `dp[i + 1][j]`

and `dp[i][j - 1]`

are not the values directly available for us, it depends on the move that our opponent make.
Then we assume our opponent is as good as we are and always makes optimize move. The worse case is that we will get the minimal value out of all possible situation after our opponent makes its move.

So the correct dp formula would be

If we pick

`dp[i][j] = max( min (dp[i + 1][j - 1], dp[i + 2][ j]) + v[i], min (dp[i][j - 2], dp[i + 1][ j - 1]) + v[j]})`

.If we pick

`i`

, then our opponent need to deal with subproblem `dp[i + 1][j]`

, it either picks from `i + 2`

or `j - 1`

. Similarly, If we pick `j`

, then our opponent need to deal with subproblem `dp[i][j - 1]`

, it either pick from `i + 1`

or `j - 2`

. We take the worse case into consideration so use min() here.```
public boolean PredictTheWinner(int[] nums) {
int n = nums.length, sum = 0;
if(n % 2 == 0) return true;
int[][] dp = new int[n][n];
for(int i=0; i < n; i++) {
dp[i][i] = nums[i];
sum += nums[i];
}
for(int j = 0; j < n; j++){
for(int i = j - 1; i >= 0; i--){
int a = (i + 1 < n && j - 1 >= 0) ? dp[i + 1][j - 1] : 0;
int b = (i + 2 < n) ? dp[i + 2][ j] : 0;
int c = (j - 2 >= 0) ? dp[i][j - 2] : 0;
dp[i][j] = Math.max(Math.min(a, b) + nums[i], Math.min(a, c) + nums[j]);
}
}
return dp[0][n - 1] * 2 >= sum;
}
```

```
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) { dp[i][i] = nums[i]; }
for (int len = 1; len < n; len++) {
for (int i = 0; i < n - len; i++) {
int j = i + len;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
```

Here is the code for O(N) space complexity:

```
public boolean PredictTheWinner(int[] nums) {
if (nums == null) { return true; }
int n = nums.length;
if ((n & 1) == 0) { return true; } // Improved with hot13399's comment.
int[] dp = new int[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (i == j) {
dp[i] = nums[i];
} else {
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
}
return dp[n - 1] >= 0;
}
```

X.https://discuss.leetcode.com/topic/76312/java-1-line-recursion-solution

X.

https://discuss.leetcode.com/topic/76319/java-dp-solution-with-explanation

We can use dynamic programming. Suppose after several rounds, the remaining array is nums[i], nums[i+1],... nums[j]

- dp[i][j] = the maximum score of player1 on subarray nums[i..j]

Player1 can choose either nums[i] or nums[j]. If nums[i] is chosen, player2 will also make best effort to get dp[i+1][j]. So for the subarray nums[i+1] ... nums[j], player1 can get:

- nums[i + 1] + nums[i + 2] + ... + nums[j] - dp[i+1][j], which is
- sum(nums[i+1] to nums[j]) - dp[i+1][j]

So we need another array sum to do range sum query, I set sum[0] to 0, sum[i] is the sum of all elements in nums before index i. so finally:

- dp[i][j] = max { sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i],

sum[j] - sum[i] - dp[i][j-1] + nums[j]}

```
public boolean PredictTheWinner(int[] nums) {
if(nums.length <= 2) return true;
int n = nums.length;
int[] sum = new int[n+1];
sum[0] = 0;
for(int i = 1; i <= n; i ++) {
sum[i] = sum[i-1] + nums[i-1];
}
int[][] dp = new int[n][n];
for(int len = 1; len < n; len ++) {
for(int i = 0; i + len < n; i ++) {
int j = i + len;
if(len == 1) dp[i][j] = Math.max(nums[i], nums[j]);
else {
int can1 = sum[j+1] - sum[i+1] - dp[i+1][j] + nums[i];
int can2 = sum[j] - sum[i] - dp[i][j-1] + nums[j];
dp[i][j] = Math.max(can1, can2);
}
}
}
return sum[n] - dp[0][n-1] <= dp[0][n-1];
}
```

https://discuss.leetcode.com/topic/76669/java-dp-solution-with-explanation

If the first player choose nums[0], the max he can get is sum( nums )-max[1, end](which is max for the second player). If the first player choose the last element in nums, then the max he can get is sum(nums)-max[0, end-1](which is the max for the second player). Thus, the DP formula is DP[start][end]=Max(sum-dp[start][end-1], sum-dp[start+1][end]).

One thing I wanna to mention is that, sum in the DP formula is not the total sum for nums, but the sum for nums[start, end].

```
public boolean PredictTheWinner(int[] nums) {
int length = nums.length;
int sum = 0;
for(int num : nums) sum+=num;
int[][] dp = new int[length][length];
for(int j = 0 ; j< length ; j++)
{
int curSum = 0;
for(int i = j ; i>= 0 ; i--)
{
curSum+=nums[i];
if(i == j) dp[i][j]=nums[j];
else
{
dp[i][j]=Math.max(curSum-dp[i][j-1], curSum-dp[i+1][j]);
}
}
}
return dp[0][length-1]*2>=sum;
}
```

http://bookshadow.com/weblog/2017/01/22/leetcode-predict-the-winner/

**Alpha-Beta搜索 + 记忆化**

## No comments:

## Post a Comment