# 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. 1 
>
>    <
>
>    \= length of the array&#x20;
>
>    <
>
>    \= 20.
> 2. Any scores in the given array are non-negative integers and will not exceed 10,000,000.
> 3. If the scores of both players are equal, then player 1 is still the winner.

## Thoughts

给定一串数字，两人依次从首或尾选一个，问有没有策略让先选的一定赢。博弈论，也就是minmax问题，即最大化自己收益 == 最小化对方收益 (最大化对方负收益)。同样对方收益也是如此定义。可以看成自己和自己玩，左右互博，因此从问题定义看就是个递归问题: 让score表示当前玩家最大收益，它等于max\_{所有选择}(选择-score(选完剩下的))。对于这道题来说，dp\[i]\[j] = max(nums\[i] - dp\[i + 1]\[j], nums\[j] - dp\[i]\[j-1])。一共有N步，用DP的话也要把问题拆成N步对应起来，虽然对每步有很多的可能状态，但最后一步只剩下一个元素，这个元素只能是nums的每个元素，因此bottom-up。

## Code

```
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        const int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MIN));
        for (int i = 0; i < n; ++i) {
            dp[i][i] = nums[i];
        }
        for (int l = 2; l <= n; ++l) {
            for (int i = 0; i <= n - l; ++i) {
                int j = i + l - 1;
                dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }

        return dp[0][n - 1] >= 0;
    }
};
```

## 时间复杂度

O(N^2)