预测赢家
给你一个整数数组 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
解法一（二维动态规划 + 零和博弈）：
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
vector <vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
{
dp[i][i] = nums[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
};
首先这是一个典型的动态规划类题型。主要特征是问题的求解需要经过多次的“选择”。在给定一串数字之后，无论选择第一个还是最后一个数字，最后的结果其实都是会剩余一串数字，然后面临和选择之前“相同”（不一定是完全相同，完全相反经过简单转化后也可以转化为相同）的问题。例如：1，2，3，4，5，6。进行选择后会变成2，3，4，5，6或者1，2，3，4，5。
题目中假设双方都会使自己获得的分数最大，那么在数字串固定的情况下，自己获得的分数最大，就会导致对方获得的分数最小。那么这样就会产生一个固定的差值。即：双方都选择对自己最有利的数字时，先选的人会比后选的人多多少分。当然，这里先选的人不一定必赢，由于数字串的顺序问题，可能会导致后选的人会赢，那么这里的差值就有可能是负数。所以我们在讨论这个问题的时候，并不需要知道双方具体能获得多少分，只要能知道双方分数的差值即可。
那么先假设一共有n个数字。由玩家1先选，玩家2后选。那么玩家1该怎么知道自己应该选择哪个数字才能使得获得的分数最高呢？首先，当玩家1选完之后，问题就转换成了再剩下n-1个数字中，玩家2要怎么选才能使得自己的分数最高。
此时，我们可以令数字串的第一个数字为a，最后一个数字为b。当玩家1选择数字a时，剩下的数字串玩家2能比玩家1多得x分。同理设玩家1选b，玩家2在剩下的字符串中能多得y分。那么玩家1在选择a的时候，最后能比玩家2多 a - x分。选择b时，能比玩家2多b - y分。那么通过比较a - x和 b - y的大小我们就能知道玩家1应该选择a还是b去获得最高分（之前提到过，数字串固定的情况下，总分是固定的，那么一方分数多，另一方分数一定少，差值就会变大。反过来说，如果差值大，就说明得分高）。同时，我们也可以知道玩家1最多能比玩家2多多少分。
接下来我们就可以将原数字串拆分为一个个小字符串了。首先是基础，当数字串长度为1的时候，显然差值就是该数字本身。
for (int i = 0; i < n; i++)
{
dp[i][i] = nums[i];
}
当数字串长度不为1的时候（ps：这里dp[i][j]的含义是nums数组中下标从i到j的数字串中，先选的人和后选的人的最大分差）。我们可以得到求最大差值的公式如下：
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
而当 j - i 的值为n -1时，就是原问题的最大差值。而由公式我们也可以知道想要求解长度为m， 以任何位置 i 为起点的数字串可获得的最大分差。就要知道长度为m - 1时以 i 和 i + 1为起点的数字串的最大分差。所以我们选择数字串的步长每次 +1。
解法二（一维动态规划）：
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
vector <int> dp(n,0);
for (int i = 0; i < n; i++)
{
dp[i] = nums[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i] = max(nums[i] - dp[i + 1], nums[j] - dp[i]);
}
}
return dp[0] >= 0;
}
};
由上面的分析可知求 dp[i][j] 时只和 dp[i][j - 1] 和 dp[i + 1][j] 有关。也就是说 dp[i][j] 和 dp[i / i +1][ 0 — j - 2] 都没有关系。也就是说，我们实际上只需要最后判断胜负的话，是不需要存储中间这些结果的，我们想要求解当前状态（数字串长度为m），只需要知道上一个状态（数字串长度为m - 1）即可。那我们就可以将解法一的二维数组优化为一维数组，然后对递推公式稍作修改即可，实际原理是一样的。