题目描述

几块石子 排成一行，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0。

返回 Alice 能够获得的最大分数。

样例

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：
在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14。
Bob 丢弃了右行，Alice 的分数现在是 11。

在第二轮中，Alice 将行分成 [6]，[2，3]。
这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。

最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。

游戏结束，因为这行只剩下一块石头了。

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

输入：stoneValue = [4]
输出：0

限制

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 10^6

算法

(动态规划) $O(n^3)$

1. 设状态 $f(l, r)$ 表示区间 $[l, r]$ 时，Alice 能获得的最大收益。预处理前缀和数组。
2. 初始时，$f(i, i) = 0$，其余待定。
3. 转移时，枚举中间点 $l \le m < r$，比较区间和 $[l, m]$ 和区间和 $[m+1, r]$，然后根据要求转移 $f(l, m) + lsum$ 或者 $f(m+1, r) + rsum$。
4. 最终答案为 $f(1, n)$。
5. 注意，此题需要用记忆化搜索实现，常数会比用循环实现小的多。这是因为循环会遍历到许多无用的状态，而记忆化搜索保证了每个到达的状态都是有意义的。

时间复杂度

• 状态数为 $O(n^2)$，每个状态需要 $O(n)$ 的时间枚举转移，故总时间复杂度为 $O(n^3)$。
• 采用记忆化搜索，常数低可以通过。

空间复杂度

• 需要 $O(n^2)$ 的空间存储状态和系统栈。

C++ 代码

#define max(x, y) ((x) > (y) ? (x) : (y))

class Solution {
private:
    vector<vector<int>> f;
    vector<int> sum;

    int solve(int l, int r) {
        if (l == r) return 0;
        if (f[l][r] > 0) return f[l][r];

        for (int m = l; m < r; m++) {
            int lsum = sum[m] - sum[l-1], rsum = sum[r] - sum[m];
            if (lsum < rsum)
                f[l][r] = max(f[l][r], solve(l, m) + lsum);
            else if (lsum == rsum)
                f[l][r] = max(f[l][r], max(solve(l, m), solve(m+1, r)) + lsum);
            else
                f[l][r] = max(f[l][r], solve(m+1, r) + rsum);
        }

        return f[l][r];
    }

public:
    int stoneGameV(vector<int>& stoneValue) {
        const int n = stoneValue.size();
        sum.resize(n+1, 0);
        f.resize(n+1, vector<int>(n+1, 0));

        for (int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + stoneValue[i-1];

        return solve(1, n);
    }
};