石子游戏 II

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

Alice 和 Bob 轮流进行，Alice 先开始。最初，M = 1。

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

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

假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 可以得到的最大数量的石头。

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：如果一开始 Alice 取了一堆，Bob 取了两堆，然后 Alice 再取两堆。Alice 可以得到 2 + 4 + 4 = 10 堆。
如果 Alice 一开始拿走了两堆，那么 Bob 可以拿走剩下的三堆。在这种情况下，Alice 得到 2 + 7 = 9 堆。返回 10，因为它更大。

示例 2:

输入：piles = [1,2,3,4,5,100]
输出：104

提示：

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

vector<vector<int>> memo;
vector<int> suffix;
int n;

int dfs(int i, int m)
{
    if (i >= n)
    {
        return 0;
    }
    if (i + 2 * m >= n)
    {
        return suffix[i];
    }
    if (memo[i][m] != -1)
    {
        return memo[i][m];
    }
    int res = 0;
    for (int x = 1; x <= 2 * m; x++)
    {
        int nextm = max(x, m);
        res = max(res, suffix[i] - dfs(i + x, nextm));
    }
    return memo[i][m] =res;
}

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        n = piles.size();
        suffix.resize(n, 0);
        suffix[n - 1] = piles[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] + piles[i];
        }
        memo.assign(n, vector<int>(n + 1, -1));
        return dfs(0, 1);
    }
};

核心思想

这题最重要的一步，是把“我能拿到多少石子”转成“当前这一段石子的总和，减去对手最优时能拿走的部分”。

因为整局游戏是零和的：某一段石子的总数是固定的，轮到当前玩家时，当前玩家拿得越多，对手就越少。

所以我们定义：

• dfs(i, m)：表示轮到当前玩家行动时，面对的是 piles[i ... n - 1] 这一段石子，并且当前 M = m，当前玩家最终最多能拿到多少石子。

其中，suffix[i] 表示从 i 到结尾的石子总和，也就是 piles[i] + ... + piles[n - 1]。

那么如果当前玩家这一步拿走了 x 堆，新的局面就是：

• 剩余区间变成 piles[i + x ... n - 1]
• 新的 M 变成 max(m, x)
• 下一回合轮到对手

在这种情况下，对手在子问题中最多能拿到 dfs(i + x, max(m, x)) 颗石子。
因此，当前玩家在这一步之后最终能拿到的石子数就是：

suffix[i] - dfs(i + x, max(m, x))

因为 suffix[i] 是当前这段石子的总和，对手拿走多少，当前玩家就少多少。

所以枚举所有合法的 x，取最大值即可：

dfs(i, m) = max_{1 <= x <= 2m} (suffix[i] - dfs(i + x, max(m, x)))

递推公式为什么正确

1. 边界情况

• 如果 i >= n，说明已经没有石子了，当前玩家能拿到 0。
• 如果 i + 2m >= n，说明当前玩家这一次最多可以拿走剩下的全部石子，所以直接返回 suffix[i]。

这一步是合法的，因为题目允许拿 1 ~ 2M 堆，而剩余堆数已经不超过 2M。

2. 状态转移

假设当前状态是 dfs(i, m)，当前玩家选择拿走 x 堆。

那么：

• 当前玩家这一步拿走了前 x 堆
• 对手面对的是剩余部分 piles[i + x ...]
• 对手的 M 更新为 max(m, x)

由于双方都采用最优策略，所以对手在这个新状态下会尽量让自己拿得更多，也就是拿到 dfs(i + x, max(m, x))。

于是当前玩家在整个后续过程中能得到的最大总收益，就是总和减去对手最优收益：

suffix[i] - dfs(i + x, max(m, x))

对所有合法的 x 取最大，就得到当前状态的最优解。

正确性证明

我们用归纳法证明 dfs(i, m) 的定义和转移都是正确的。

归纳基

当 i >= n 时，没有石子，返回 0 正确。

当 i + 2m >= n 时，当前玩家可以一次性拿完剩余所有石子，所以返回 suffix[i] 正确。

归纳假设

假设对于所有更靠后的状态，dfs 都能正确表示“轮到当前玩家时最多能拿到的石子数”。

归纳推导

在状态 dfs(i, m) 下，当前玩家必须从 1 ~ 2m 中选择一个合法的 x。

选定 x 后，游戏就变成了一个更小的子问题 dfs(i + x, max(m, x))。
根据归纳假设，这个子问题的结果是正确的。

由于当前区间总和固定为 suffix[i]，所以当前玩家最终能拿到的石子数一定等于：

suffix[i] - dfs(i + x, max(m, x))

对所有合法的 x 取最大值，就是当前玩家能达到的最优结果。

因此 dfs(i, m) 的定义成立，递推也成立，命题得证。

复杂度分析

• 状态数：i 有 n 种取值，m 最多到 n，所以状态数是 O(n^2)
• 每个状态需要枚举 x = 1 ~ 2m，最坏是 O(n)

所以总时间复杂度是 O(n^3)，空间复杂度是 O(n^2)。

由于题目里 n <= 100，这个复杂度是完全可以接受的。