5766. 石子游戏 VIII

好吧，这次没有调出来，所以还是记录一下
但它和黑妹的游戏II 是非常相似的
思路：
对于ALICE和BOB，每次获得的分数即为前缀和，那么
令dp[i]表示当前选择i的人能获得的当前分数-对手分数的最大差值
倒推，dp[i] = max(dp[i],sum[i] - dp[i+1]);
而因为选择个数>=2，则对于ALICE来说1必选
故答案为dp[1]

但是为什么初始化不同呢？
因为在黑妹的游戏这里，对手的状态在我的状态之后
而本题中，我的状态在对手的状态之后
所以初始化是不同的

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        vector<int> psum(stones.size()+1, 0);
        int n=stones.size();
        for (int i=0; i<n; ++i) {
            psum[i+1]=psum[i]+stones[i];
        }
        vector<int> dp(stones.size(), 0);
        int mx=psum[n];
        for (int i=n-1; ~i; --i) {
            dp[i]=mx;
            mx=max(mx, psum[i]-dp[i]);
        }
        return dp[1];
    }
};