题目地址：https://leetcode.com/problems/predict-the-winner/?tab=Description
题意大概是两个人，每次分别从首或尾取一个值，问第一个人获得的值大的情况。
这有点博弈论的意思，但主要还是dp。不过我是用计搜写出来的
bool PredictTheWinner(vector<int>& nums) {
return win(nums, 0, 0, 0, nums.size()-1, true);
}
bool win(vector<int>& nums, int sum1, int sum2, int start, int end, bool is1) {
if (start > end) {
if (sum1 >= sum2) return is1;
else return !is1;
}
if (is1) {
return !(win(nums, sum1+nums[start], sum2, start+1, end, !is1) && win(nums, sum1+nums[end], sum2, start, end-1, !is1));
} else {
return !(win(nums, sum1, sum2+nums[start], start+1, end, !is1) && win(nums, sum1, sum2+nums[end], start, end-1, !is1));
}
}
然后看了一下别人的解决方案
dp[i][j]为在i－j之间能取到最大方案，最后判断dp[0][n-1]是否大于0
所以可以把这两个人的分别取值当做一加一减，每次取能添加点减去之前的dp值的最大值为当前状态最优来进行更新
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 = 1; len < n; ++len) {
for (int i = 0, j = len; j < n; ++i, ++j) {
dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
显然，这题计搜比dp好理解太多
