题目描述

给你一个整数数组 nums。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true。你可以假设每个玩家的玩法都会使他的分数最大化。

样例

输入：[1, 5, 2]
输出：False
解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择
。如果玩家 2 选择了 5，那么玩家 1 则只剩下 1（或者 2 ）可选。 
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5。
因此，玩家 1 永远不会成为赢家，返回 false。

输入：[1, 5, 233, 7]
输出：True
解释：玩家 1 一开始选择 1。然后玩家 2 必须从 5 和 7 中进行选择。
无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，
所以返回 true，表示玩家 1 可以成为赢家。

限制

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 10^7

算法1

(动态规划) $O(n^2)$

1. 从最简单的问题开始考虑，假设只有一个数字，则只能玩家 A 选择这个数字。
2. 接着，问题的规模开始扩大，扩大后，两个玩家会有两种决策，一种是选择数组头部，一种是选择数组尾部，而这两种情况下的子问题都可以提前计算出。至此，动态规划的思路已经很明显。
3. 设 $f(i, j)$ 表示闭区间 [i, j] 下玩家 A 所能获得的最大分数。
4. 初始时，若最后一次是玩家 A 取数，则 $f(i, i) = nums[i]$；否则 $f(i, i) = 0$。。
5. 每次 $f(i, j)$ 转移有两种情况：当这一次是玩家 A 取数时，$f(i, j) = \max (f(i + 1, j) + nums[i], f(i, j - 1) + nums[j])$ 表示从头部取或者从尾部取，二者最优；当这一次是玩家 B 取数时，玩家B肯定希望自己的得分最大，这必然会导致玩家 A 的得分变小，故此时 $f(i, j) = \min (f(i + 1, j), f(i, j - 1))$。
6. 最后玩家 A 能获得的最大得分就是 $f(0, n - 1)$。

时间复杂度

• 动态规划的状态数为 $O(n^2)$，每次只需要 $O(1)$ 的时间转移，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要空间存储动态规划数组，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(n, 0));

        int turn = n & 1;
        for (int i = 0; i < n; i++) {
            if (turn)
                f[i][i] = nums[i];
            else
                f[i][i] = 0;
        }

        for (int len = 2; len <= n; len++) {
            turn ^= 1;
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (turn)
                    f[i][j] = max(f[i + 1][j] + nums[i], f[i][j - 1] + nums[j]);
                else
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]);
            }
        }

        return 2 * f[0][n - 1] >= accumulate(nums.begin(), nums.end(), 0);
    }
};

算法2

(动态规划) $O(n^2)$

1. 我们可以简化算法 1 中的状态表示，我们设 $f(i, j)$ 表示闭区间 [i, j] 下，先手玩家与后手玩家的得分差距的最大值。
2. 初始时，$f(i, i) = nums[i]$。
3. 转移时，$f(i, j) = \max (-f(i + 1, j) + nums[i], -f(i, j - 1) + nums[j])$。这里的含义为，因为此时是先手玩家，被转移的区间就是后手玩家的得分，所以需要 取相反数 然后转移。
4. 最后我们只需要判断 $f(i, j)$ 是否大于等于 0。

时间复杂度

• 动态规划的状态数为 $O(n^2)$，每次只需要 $O(1)$ 的时间转移，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要空间存储动态规划数组，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++)
            f[i][i] = nums[i];

        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                f[i][j] = max(-f[i + 1][j] + nums[i], -f[i][j - 1] + nums[j]);
            }

        return f[0][n - 1] >= 0;
    }
};