题目
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
输入：nums = [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 。示例 2：
输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。提示：
1 <= nums.length <= 200 <= nums[i] <= 107
解答
- 动态规划
首先，我们可以把这个问题看成是两个玩家在一堆石头上进行取石子游戏。每个玩家都可以在任何时候从石堆中取出一些石头，但是每次取石头的数量不能超过石堆中剩余石头的数量。游戏的规则是先手玩家必须先取，然后轮流取石头，直到石堆为空。每个石头的价值都不同，每个玩家在取石头时可以获得相应的价值。
我们可以用动态规划来解决这个问题。假设nums数组的长度为n，dp[i][j]表示在nums[i...j]范围内，先手玩家能获得的最大分数，那么先手玩家最终获胜的条件是dp[0][n-1]不小于nums中所有数之和的一半。
接下来考虑如何计算dp数组。首先，我们可以很容易地得出当区间长度为1时，dp[i][i]的值就是nums[i]。这是因为当只有一个数时，先手玩家必定获胜，得分为该数。
接下来，我们需要考虑更长的区间。假设当前处理的区间长度为len，则可以枚举区间左端点i，然后通过递推式来计算dp[i][j]。对于区间[i,j]，先手玩家可以选择i或j作为自己的选择，那么后手玩家就会在[i+1, j]或[i, j-1]区间内变成先手玩家。这样转化后的问题就可以通过dp数组的计算得到解决。
具体地，假设先手玩家选择了左端点i，那么后手玩家就会在[i+1, j]区间内变成先手玩家，此时先手玩家能获得的最大分数就是nums[i]加上区间[i+2,j]或区间[i+1,j-1]内先手玩家能获得的最大分数的最小值，即：
left = nums[i] + min(dp[i+2][j], dp[i+1][j-1])同样地，假设先手玩家选择了右端点j，那么后手玩家就会在[i, j-1]区间内变成先手玩家，此时先手玩家能获得的最大分数就是nums[j]加上区间[i,j-2]或区间[i+1,j-1]内先手玩家能获得的最大分数的最小值，即：
right = nums[j] + min(dp[i][j-2], dp[i+1][j-1])由于先手玩家和后手玩家的取石头顺序是交替进行的，因此先手玩家和后手玩家在不同的区间上作为先手玩家和后手玩家的情况应该分别考虑。最终，dp[i][j]的值就是left和right中的较大值，即：
dp[i][j] = max(left, right)最终的答案就是dp[0][n-1]是否大于等于nums中所有数之和的一半。
代码实现时，我们可以使用二维数组dp来保存先手玩家能获得的最大分数，然后用双重循环来枚举区间长度和区间左端点，并使用上述递推式来计算dp数组中的每个元素。最后，比较dp[0][n-1]和nums中所有数之和的一半即可得到答案。
class Solution {
public:
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n)); // 定义二维dp数组，dp[i][j]表示当剩下的数是nums[i..j]时，先手玩家比后手玩家多得的最大分数。
// 处理区间长度为1的情况
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i]; // 当剩下的数只有一个时，先手玩家只能取这个数，并且得分就是这个数本身。
}
// 处理更长的区间
for (int len = 2; len <= n; len++) { // 枚举区间长度
for (int i = 0; i <= n - len; i++) { // 枚举区间左端点
int j = i + len - 1; // 区间右端点
int left = nums[i] + min(i+2 <= j ? dp[i+2][j] : 0, i+1 <= j-1 ? dp[i+1][j-1] : 0); // 先手玩家取nums[i]后，后手玩家就成为了先手玩家，接下来剩下的数就是nums[i+1..j]，此时先手玩家能得到的最大分数是dp[i+1][j]。如果先手玩家取nums[i]后，后手玩家也取了一个数，那么接下来剩下的数就是nums[i+2..j]，此时先手玩家能得到的最大分数是dp[i+2][j]。由于后手玩家也是聪明的，他肯定会选择让先手玩家得到更少的分数，因此先手玩家能得到的最大分数就是nums[i]加上min(dp[i+2][j], dp[i+1][j-1])。同理，我们也可以计算出先手玩家取nums[j]时能得到的最大分数right。
int right = nums[j] + min(i <= j-2 ? dp[i][j-2] : 0, i+1 <= j-1 ? dp[i+1][j-1] : 0);
dp[i][j] = max(left, right); // 取left和right的较大值，表示先手玩家在nums[i..j]这个区间内能得到的最大分数。
}
}
// 判断先手玩家是否能获胜
return dp[0][n-1] >= accumulate(nums.begin(), nums.end(), 0) / 2.0; // 如果先手玩家能得到的最大分数不小于nums中所有数之和的一半，那么先手玩家就能获胜。
}
};