题目描述

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的 所有 石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

样例

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。
在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 

如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。
在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。

所以我们返回更大的 10。 

限制

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10 ^ 4

算法

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

1. $f(i, j)$ 表示当前位于第 $i$ 个位置且 M 为 $j$ 时，先手能取到的最大的石子数量。
2. 我们需要从后往前转移，因为最后的状态我们都是可以直接得到的。维护后缀和 $sum$。
3. 有效位置的下标从 0 到 $n - 1$，M 的下标从 1 到 $n$。初始化：对于所有的 $1 \le j \le n$，$f(n, j) = 0$。这是边界情况。
4. 转移时，我们需要枚举这一次先手取多少个石子 $k$，满足 $1 \le k \le 2 * j$，且 $i + k \le n$（$i + k = n$ 就是后边的石子全部取完），我们转移 $f(i, j) = \max(f(i, j), sum(i) - f(i + k, \max(j, k)))$。这里用 $sum(i)$ 减的原因是，此时我们交换了先后手，被转移的先手 以当前状态的角度看是后手，所以需要从总和里去除。
5. 最后答案就是 $f(0, 1)$，表示当前在第 0 个位置，且 M 为 1 时先手能取到的最大值。

时间复杂度

• 状态数为 $O(n^2)$ 个，转移需要 $O(n)$ 的时间，故时间复杂度为 $O(n^3)$。

空间复杂度

• 需要 $O(n^2)$ 的数组记录状态，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> sum(n + 1, 0);
        vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));

        for (int i = n - 1; i >= 0; i--)
            sum[i] = sum[i + 1] + piles[i];

        for (int i = n - 1; i >= 0; i--)
            for (int j = 1; j <= n; j++)
                for (int k = 1; k <= 2 * j && i + k <= n; k++)
                    f[i][j] = max(f[i][j], sum[i] - f[i + k][max(j, k)]);

        return f[0][1];
    }
};