5627. 石子游戏 VII
区间dp
f[l][r]表示：先手的分数-后手分数的最大值
class Solution {
public:
int stoneGameVII(vector<int>& st) {
int n=st.size();
int pre[n+1];
pre[0]=0;
for(int i=0;i<n;i++)pre[i+1]=pre[i]+st[i];
int f[n+1][n+1];
memset(f,0,sizeof f);
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int l=i,r=i+len-1;
// cout<<f[l][r]<<endl;
f[l][r]=max(pre[r]-pre[l]-f[l+1][r],pre[r-1]-pre[l-1]-f[l][r-1]);
}
}
return f[1][n];
}
};
网友评论