题目地址：
https://leetcode.com/problems/predict-the-winner/
给定一个非负整数数组。设计一个两人的游戏，比如甲乙两个人，甲可以从数组左右两端点取一个分数，然后乙接着拿，直到拿完为止。如果甲总分高于等于乙，就返回true，否则返回false。甲是先手方。
思路是这样的：如果只剩两个数字了，那么结论可以很轻易的得到。如果多于两个数字，那么就枚举先手方拿左右端这两种情况，这样就把大问题化为了更小规模的问题。但困难之处在于，仅仅知道小规模问题谁胜谁负，不足以知道大规模问题谁胜谁负，于是想到我们可以把谁胜谁负转化为分差。如果我们知道了n规模的问题中，先手方比后手方的分差sn，那么对于规模n+1的问题，先手方比后手方的分差就是先手方拿一个分数，再减去规模为n的问题中先手方和后手方的分差（此时先后手对调了）。最后只需要返回分差是否非负即可。
法1：DFS+记忆化。
public class Solution {
public boolean PredictTheWinner(int[] nums) {
// 如果只有一个数字，返回true，先手必胜
if (nums.length == 1) {
return true;
}
// f[i][j]记录对于数组nums[i,...,j]，先手方与后手方的分差
// 做记忆化，防止重复搜索
int[][] f = new int[nums.length][nums.length];
return dfs(nums, 0, nums.length - 1, f) >= 0;
}
private int dfs(int[] nums, int i, int j, int[][] f) {
// 递归出口
if (j - i == 1) {
f[i][j] = Math.abs(nums[i] - nums[j]);
return f[i][j];
}
// 如果f里有记忆，直接调取记忆；否则接着暴搜
// score1是先手选了数组左端的情况下，后手与先手的分差
int score1 = f[i + 1][j] != 0 ? f[i + 1][j] : dfs(nums, i + 1, j, f);
// score2是先手选了数组右端的情况下，后手与先手的分差
int score2 = f[i][j - 1] != 0 ? f[i][j - 1] : dfs(nums, i, j - 1, f);
// 返回之前做一下记忆
f[i][j] = Math.max(nums[i] - score1, nums[j] - score2);
return f[i][j];
}
}
时空复杂度O(n2)。时间复杂度的分析可以这么看，在暴搜那个二维矩阵的时候，每搜到叶子节点回溯的时候，一路上都会去做记忆化，所以这个二维矩阵每个entry最多被搜一次。
法2：动态规划。本质上和记忆化搜索是一样的。只需要注意更新顺序，一定要以已知来更新未知。
public class Solution {
public boolean PredictTheWinner(int[] nums) {
if (nums.length == 1) {
return true;
}
int[][] dp = new int[nums.length - 1][nums.length];
for (int j = 1; j < nums.length; j++) {
for (int i = j - 1; i >= 0; i--) {
if (j - i == 1) {
dp[i][j] = Math.abs(nums[i] - nums[j]);
} else {
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
}
return dp[0][nums.length - 1] >= 0;
}
}
时空复杂度一样。
接下来考虑优化空间复杂度，直观的想法是只用一维数组，重用数组覆盖掉以后不用的数值。我们想象某时刻我们在更新矩阵的第i行第j列，这个数字只依赖与第i行第j−1列，以及第i+1行第j列的数，所以我们可以按行滚动更新，具体的意思是，我们初始化一维数组，代表某一行，然后新行就用这个旧的行来更新，在更新行的时候，j需要从左向右更新。在空间优化的时候，决定更新顺序的关键，是一定要用已经算出来的值更新未知的值，只有这样才能保证答案正确。代码如下：
public class Solution {
public boolean PredictTheWinner(int[] nums) {
if (nums.length == 1) {
return true;
}
int[] dp = new int[nums.length];
for (int i = nums.length - 2; i >= 0; i--) {
for (int j = i + 1; j < nums.length; j++) {
if (j - i == 1) {
dp[j] = Math.abs(nums[i] - nums[j]);
} else {
dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
}
}
}
return dp[nums.length - 1] >= 0;
}
}
时间复杂度一样，空间O(n)。