Description
给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/predict-the-winner
思考和编码过程
这一题其实之前见过，是要用区间dp的。不过肯定不能直接用胜负情况来定义dp，不然无法递推。换个角度，这里用最大获取的分数。于是一开始的把状态定义为dp(i,j,k)，当k=0时，为1号玩家在数组区间为i到j时开始操作所能得到的最大分数，当k=1时，为2号玩家在数组区间为i到j时开始操作所能得到的最大分数。然后写了状态转换方程后，发现其实k是不需要的，状态只需要保留区间信息i和j就行了，最后的结果可以直接使用dp(0,n-1)来判断。最后的方程为
dp(i,j)=max{sum(i+1,j)-dp(i,j)+nums[i], sum(i,j-1)-dp(i,j-1)+nums[j]
其中需要预处理sum数组来o(1)的得到nums在区间i到j的和。
编码过程中一开始没考虑到用记忆化搜索还是递推。按照递推的方式写的，一开始的变量没有定义成全局变量，后来发现这个的递推不会写，于是改用记忆化搜索，并将已经定义的变量作为参数传入DP函数中。期间尝试着用匿名函数来获取sum(i,j)
auto f=[&](int i,int j)->int{return sum[j+1]-sum[i];};
可是传入函数参数时，这个函数指针比不知道怎么写，因为匿名函数里其实还引用了外部变量，百度后发现可以用function类模板，不过要添加<functional>头文件。地址在这https://blog.csdn.net/qq_35721743/article/details/83217416
之后看了题解，原来只要考虑胜负情况所以sum数组是可以不要的，然后学习了一下这个的递推写法。
class Solution {
public:
// int DP(vector<vector<int>> & dp,int i,int j,function<int(int,int)> f,vector<int> & nums){
// if(dp[i][j]) return dp[i][j];
// if(i==j) return nums[i];
// int S1=f(i+1,j)-DP(dp,i+1,j,f,nums)+nums[i];
// int S2=f(i,j-1)-DP(dp,i,j-1,f,nums)+nums[j];
// return dp[i][j]=max(S1,S2);
// }
bool PredictTheWinner(vector<int>& nums) {
int n=nums.size();
//vector<int> sum(n+1);
//sum[0]=0;
////for(int i=1;i<=n;++i) sum[i]=sum[i-1]+nums[i-1];
//auto f=[&](int i,int j)->int{return sum[j+1]-sum[i];};
vector<vector<int>> dp(n);
for(auto & it:dp) it.resize(n);
// int tmp=DP(dp,0,n-1,f,nums);
// return tmp*2>=f(0,n-1);
for(int i=0;i<n;++i)
dp[i][i]=nums[i];
for(int i=n-1;i>=0;--i)
for(int j=i+1;j<n;++j)
dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1]);
return dp[0][n-1]>=0;
}
};
用markdown编辑的界面还挺好看的～
