5627. 石子游戏 VII（区间dp）

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];
    }
};