题目分析

这是第219场周赛的第三题，这个题目难度不大，还记得我之前说过的思路吗？遇到博弈的题型，一般要去寻找贪心，动态规划和数学这三个方法，小伙伴们先想一想爱丽丝和鲍勃之间的胜败关系是如何转化的。

动态规划

**用dp[i][j]表示从i到j区间爱丽丝先手，最后得分的差值。那么爱丽丝可以有两种选择，一个是取第i个石子，也可以取第j个石子。取第i个石子就变成了dp[i + 1][j]，此时是鲍勃先手，代表鲍勃与爱丽丝的差值。因此爱丽丝与鲍勃之间的差值是-dp[i + 1][j]，而且爱丽丝取第i个石子后，还要加上剩余石子的得分，即stones[i + 1] + … + stones[j]。同理，如果取第j个石子，就是-dp[i][j - 1] + stones[i] + … + stones[j - 1]**。所以状态转移方程可得
$$dp[i][j] = max(-dp[i + 1][j] + cursum[j + 1] - cursum[i + 1], -dp[i][j - 1] + cursum[j] - cursum[i])$$

其中cursum[i]是前i - 1个元素之和，称为前缀和。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n^2)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int length = stones.size();
        vector<int> cursum(length + 1);
        vector<vector<int>> dp(length, vector<int>(length));
        for (int i = 1; i < length + 1; i++) {
            cursum[i] = cursum[i - 1] + stones[i - 1];
        }
        for (int l = 1; l < length; l++) {
            for (int i = 0; i < length - l; i++) {
                int j = i + l;
                dp[i][j] = max(-dp[i + 1][j] + cursum[j + 1] - cursum[i + 1], -dp[i][j - 1] + cursum[j] - cursum[i]);
            }
        }
        return dp[0].back();
    }
};

刷题总结

博弈的题目是非常有意思的，第一次做这种题型可能会有一些懵，多做一些就明白了其中的道理。