石子游戏 II
字数 2663 2025-11-08 10:02:38

石子游戏 II

题目描述

给定一个整数数组 piles，表示一排石子堆，每堆石子数量为 piles[i]。Alice 和 Bob 轮流进行游戏，Alice 先手。在每一轮中，玩家可以取走当前最左边的 X 堆石子，其中 1 <= X <= 2M。然后，将 M 更新为 max(M, X)。游戏持续到所有石子都被取走。假设 Alice 和 Bob 都发挥出最佳水平，目标是让 Alice 能够获得的最大石子总数。

解题过程

  1. 问题分析
    这是一个双人零和博弈问题。与标准的“石子游戏”不同，玩家每次可以取走的堆数 X 是动态变化的，它取决于一个状态变量 M，而 M 又会在每次操作后更新。这增加了问题的复杂性。我们需要一个动态规划状态来记录当前剩余石子堆的起始位置以及当前的 M 值。

  2. 定义状态
    设 dp[i][m] 表示当游戏进行到石子堆从第 i 堆（0-indexed）开始，并且当前的 M 值为 m 时，当前行动的玩家（无论是 Alice 还是 Bob）能够比对手多获得的最大石子总数。
    注意：这里的“当前玩家”是相对于状态 (i, m) 而言的。

  3. 状态转移方程
    在当前状态 (i, m) 下，当前玩家可以选择取走 X 堆石子，其中 X 的取值范围是 1 到 2m。当然，X 不能超过剩余的石子堆数，即 X <= n - i。
    如果玩家取走了 X 堆石子（即从 i 到 i + X - 1），那么他立即获得这些堆的石子总数，记为 stonesTaken = piles[i] + piles[i+1] + ... + piles[i+X-1]。
    取走后，游戏状态变为：剩余石子堆从第 i + X 堆开始，新的 M 值变为 newM = max(m, X)。
    此时，轮到对手行动。在状态 (i+X, newM) 下，对手作为“当前玩家”，会采取最优策略，从而获得相对于“下一个玩家”（即原来的玩家）的最大优势分数，这个分数就是 dp[i+X][newM]。
    那么，对于当前玩家而言，他这次选择 X 所带来的净优势是多少呢？

    • 他通过这次取石子，直接获得了 stonesTaken 的分数。
    • 但是，接下来对手在状态 (i+X, newM) 下行动，会获得相对于他的优势 dp[i+X][newM]。这意味着，当前玩家相对于对手的优势会减少 dp[i+X][newM]。
      因此，选择 X 后，当前玩家相对于对手的净优势为：stonesTaken - dp[i+X][newM]。
      当前玩家的目标就是最大化这个净优势。所以状态转移方程为：
      dp[i][m] = max( stonesTaken - dp[i+X][max(m, X)] )，其中 X 取遍 1 到 min(2m, n-i)。

  4. 边界条件
    当没有石子剩余时，即 i == n，任何玩家都无法再获得石子，所以 dp[n][m] = 0。

  5. 计算顺序与预处理

    • 由于状态 dp[i][m] 依赖于 dp[i+X][newM]，其中 i+X > i，所以我们需要从右向左遍历 i（即从石子堆的末尾开始计算）。
    • m 的最大值是多少？在最开始，M=1。每次取石子的堆数 X 最多可以达到 2m，而新的 M 会变成 max(m, X)。理论上，m 最大可以达到 n（当某次取了所有剩余石子时）。所以 m 的维度可以设为 n+1。
    • 为了快速计算任意连续子数组的和（即 stonesTaken），我们可以预先计算一个前缀和数组 prefixSum，使得 prefixSum[i] 表示 piles[0] + piles[1] + ... + piles[i-1]。这样，从 i 到 j 的石子数和就是 prefixSum[j+1] - prefixSum[i]。在我们的状态转移中，stonesTaken = prefixSum[i+X] - prefixSum[i]。

  6. 最终结果
    游戏的初始状态是：剩余石子堆从第 0 堆开始，M=1。当前行动的玩家是 Alice。
    我们要求的是 Alice 能获得的最大石子总数。
    设总石子数为 total = sum(piles)。
    根据 dp[0][1] 的定义：它是 Alice 在初始状态下，相对于 Bob 所能获得的最大优势分数。
    假设 Alice 最终获得 A 分，Bob 获得 B 分，有 A + B = total。
    根据优势分数的定义，有 A - B = dp[0][1]。
    解这个方程组：A = (total + dp[0][1]) / 2。
    因为题目保证石子总数为正整数，所以 (total + dp[0][1]) 一定是偶数，结果即为整数。

  7. 算法步骤总结
    a. 计算数组长度 n。
    b. 计算前缀和数组 prefixSum。
    c. 初始化一个二维数组 dp，维度为 (n+1) x (n+1)，所有值初始化为一个很小的数（或0，但边界条件会覆盖）。
    d. 将 dp[n][m]（对于所有 m）设为 0（边界条件）。
    e. 从 i = n-1 开始，向下遍历到 i = 0。
    f. 对于每个 i，遍历所有可能的 m（从 1 到 n，但 m 很大时可能没有对应的 X，可以适当剪枝，或者遍历到 n 也无妨）。
    g. 对于每个 (i, m)，遍历所有可能的 X（从 1 到 min(2*m, n-i)）。
    h. 计算本次取走的石子数 stonesTaken = prefixSum[i+X] - prefixSum[i]。
    i. 计算新的 M：newM = max(m, X)。
    j. 状态转移：dp[i][m] = max(dp[i][m], stonesTaken - dp[i+X][newM])。
    k. 遍历结束后，计算总石子数 total = prefixSum[n]。
    l. 最终结果 (total + dp[0][1]) / 2。

通过这个循序渐进的推导和计算过程，我们就可以解决“石子游戏 II”这个区间动态规划问题。

石子游戏 II 题目描述 给定一个整数数组 piles ，表示一排石子堆，每堆石子数量为 piles[i] 。Alice 和 Bob 轮流进行游戏，Alice 先手。在每一轮中，玩家可以取走当前最左边的 X 堆石子，其中 1 <= X <= 2M 。然后，将 M 更新为 max(M, X) 。游戏持续到所有石子都被取走。假设 Alice 和 Bob 都发挥出最佳水平，目标是让 Alice 能够获得的最大石子总数。 解题过程 问题分析 这是一个双人零和博弈问题。与标准的“石子游戏”不同，玩家每次可以取走的堆数 X 是动态变化的，它取决于一个状态变量 M ，而 M 又会在每次操作后更新。这增加了问题的复杂性。我们需要一个动态规划状态来记录当前剩余石子堆的起始位置以及当前的 M 值。 定义状态 设 dp[i][m] 表示当游戏进行到石子堆从第 i 堆（0-indexed）开始，并且当前的 M 值为 m 时，当前行动的玩家（无论是 Alice 还是 Bob）能够比对手多获得的最大石子总数。 注意：这里的“当前玩家”是相对于状态 (i, m) 而言的。 状态转移方程 在当前状态 (i, m) 下，当前玩家可以选择取走 X 堆石子，其中 X 的取值范围是 1 到 2m 。当然， X 不能超过剩余的石子堆数，即 X <= n - i 。 如果玩家取走了 X 堆石子（即从 i 到 i + X - 1 ），那么他立即获得这些堆的石子总数，记为 stonesTaken = piles[i] + piles[i+1] + ... + piles[i+X-1] 。 取走后，游戏状态变为：剩余石子堆从第 i + X 堆开始，新的 M 值变为 newM = max(m, X) 。 此时，轮到对手行动。在状态 (i+X, newM) 下，对手作为“当前玩家”，会采取最优策略，从而获得相对于“下一个玩家”（即原来的玩家）的最大优势分数，这个分数就是 dp[i+X][newM] 。 那么，对于当前玩家而言，他这次选择 X 所带来的净优势是多少呢？ 他通过这次取石子，直接获得了 stonesTaken 的分数。 但是，接下来对手在状态 (i+X, newM) 下行动，会获得相对于他的优势 dp[i+X][newM] 。这意味着，当前玩家相对于对手的优势会减少 dp[i+X][newM] 。 因此，选择 X 后，当前玩家相对于对手的净优势为： stonesTaken - dp[i+X][newM] 。 当前玩家的目标就是最大化这个净优势。所以状态转移方程为： dp[i][m] = max( stonesTaken - dp[i+X][max(m, X)] ) ，其中 X 取遍 1 到 min(2m, n-i) 。 边界条件 当没有石子剩余时，即 i == n ，任何玩家都无法再获得石子，所以 dp[n][m] = 0 。 计算顺序与预处理 由于状态 dp[i][m] 依赖于 dp[i+X][newM] ，其中 i+X > i ，所以我们需要从右向左遍历 i （即从石子堆的末尾开始计算）。 m 的最大值是多少？在最开始， M=1 。每次取石子的堆数 X 最多可以达到 2m ，而新的 M 会变成 max(m, X) 。理论上， m 最大可以达到 n （当某次取了所有剩余石子时）。所以 m 的维度可以设为 n+1 。 为了快速计算任意连续子数组的和（即 stonesTaken ），我们可以预先计算一个前缀和数组 prefixSum ，使得 prefixSum[i] 表示 piles[0] + piles[1] + ... + piles[i-1] 。这样，从 i 到 j 的石子数和就是 prefixSum[j+1] - prefixSum[i] 。在我们的状态转移中， stonesTaken = prefixSum[i+X] - prefixSum[i] 。 最终结果 游戏的初始状态是：剩余石子堆从第 0 堆开始， M=1 。当前行动的玩家是 Alice。 我们要求的是 Alice 能获得的最大石子总数。 设总石子数为 total = sum(piles) 。 根据 dp[0][1] 的定义：它是 Alice 在初始状态下，相对于 Bob 所能获得的最大优势分数。 假设 Alice 最终获得 A 分，Bob 获得 B 分，有 A + B = total 。 根据优势分数的定义，有 A - B = dp[0][1] 。 解这个方程组： A = (total + dp[0][1]) / 2 。 因为题目保证石子总数为正整数，所以 (total + dp[0][1]) 一定是偶数，结果即为整数。 算法步骤总结 a. 计算数组长度 n 。 b. 计算前缀和数组 prefixSum 。 c. 初始化一个二维数组 dp ，维度为 (n+1) x (n+1) ，所有值初始化为一个很小的数（或0，但边界条件会覆盖）。 d. 将 dp[n][m] （对于所有 m ）设为 0（边界条件）。 e. 从 i = n-1 开始，向下遍历到 i = 0 。 f. 对于每个 i ，遍历所有可能的 m （从 1 到 n ，但 m 很大时可能没有对应的 X ，可以适当剪枝，或者遍历到 n 也无妨）。 g. 对于每个 (i, m) ，遍历所有可能的 X （从 1 到 min(2*m, n-i) ）。 h. 计算本次取走的石子数 stonesTaken = prefixSum[i+X] - prefixSum[i] 。 i. 计算新的 M ： newM = max(m, X) 。 j. 状态转移： dp[i][m] = max(dp[i][m], stonesTaken - dp[i+X][newM]) 。 k. 遍历结束后，计算总石子数 total = prefixSum[n] 。 l. 最终结果 (total + dp[0][1]) / 2 。 通过这个循序渐进的推导和计算过程，我们就可以解决“石子游戏 II”这个区间动态规划问题。