区间dp,f[i][j]表示区间[i,j]内 player1 比 player2 多获取的分数
C++ 代码
class Solution {
public:
bool predictTheWinner(vector<int>& nums) {
int n = nums.size();
// the diff between player1 and player2
vector<vector<int>> f(n, vector<int>(n, 0));
for(int i=0; i<n; ++i)f[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;
// max(player2从左边拿,player2从右边拿)
f[i][j] = max(-f[i+1][j] + nums[i], -f[i][j-1] + nums[j]);
}
}
return f[0][n-1] >= 0;
}
};