LeetCode 1690. 石子游戏 VII

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
数组 动态规划 数学 博弈 极小化极大

题目描述

✅ 1690. 石子游戏 VII

image-20260929090832171

image-20260929090832281

题意分析

两人轮流移除最左或最右的一颗石子，每轮获得的是移除后剩余石子的总和。Alice 先手，希望最终的 Alice得分-Bob得分 尽量大；Bob 希望这个差尽量小。要求双方都按各自目标行动时的最终分差。

解法：区间 DP

核心思路

[!blue]
把状态统一成当前玩家相对对手的最优分差。 dp[l][r] 表示只剩区间 [l,r] 时，从现在开始“当前玩家新增得分减去对手新增得分”的最大值。Bob 减小 Alice 的领先，也就是增大自己的领先，所以双方都能使用同一状态，不必额外记录是谁行动。

若当前玩家移除左端，本轮得到 sum(l+1,r)，接下来的 [l+1,r] 由对手先行动。子问题 dp[l+1][r] 保存的是对手相对本方的领先，因此换回本方视角，最终分差为 sum(l+1,r)-dp[l+1][r]。

移除右端同理，候选分差为 sum(l,r-1)-dp[l][r-1]。当前玩家只有这两种合法选择，取较大值即可；每个子问题又已包含对手的最优应对，转移就同时落实了双方的选择。

过去已经获得的分数在当前两种选择下都是同一个常量，不影响后续最优决策，因此无需放进状态。单元素区间移除后已无石子，最后一轮得分为 0，故 dp[i][i]=0。每个转移只依赖长度少一的区间，按区间长度递增计算即可。

解题步骤

  1. 构建 prefix[i]，表示前 i 颗石子的总和，区间 [a,b] 的和为 prefix[b+1]-prefix[a]。
  2. 初始化区间 DP 为 0，从长度 2 开始枚举所有 [l,r]。
  3. 删除左端后的和为 prefix[r+1]-prefix[l+1]，删除右端后的和为 prefix[r]-prefix[l]，分别减去对应子问题分差。
  4. 两个候选取最大值写入 dp[l][r]，最后返回 dp[0][n-1]。

只剩两颗石子时，对手最后一轮得 0，当前玩家应留下较大的一颗获得其分值。更长区间则必须同时考虑子问题分差，不能只按本轮得分决定删除哪一端。

代码实现

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        // 带哨兵位的前缀和，sum(a, b) = prefix[b + 1] - prefix[a]。
        int[] prefix = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        // dp[l][l] = 0 由零值初始化天然满足。
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                // 这里计算移除左端后剩余部分的和，不是被拿走的石子值。
                int sumLeft = prefix[r + 1] - prefix[l + 1];
                int sumRight = prefix[r] - prefix[l];
                // 减去子问题结果，编码「对手也在最优行动」。
                int takeLeft = sumLeft - dp[l + 1][r];
                int takeRight = sumRight - dp[l][r - 1];

                dp[l][r] = Math.max(takeLeft, takeRight);
            }
        }

        return dp[0][n - 1];
    }
}

func stoneGameVII(stones []int) int {
    n := len(stones)
    // 带哨兵位的前缀和，sum(a, b) = prefix[b+1] - prefix[a]。
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }

    // dp[l][l] = 0 由零值初始化天然满足。
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }

    for length := 2; length <= n; length++ {
        for l := 0; l+length-1 < n; l++ {
            r := l + length - 1
            // 这里计算移除左端后剩余部分的和，不是被拿走的石子值。
            sumLeft := prefix[r+1] - prefix[l+1]
            sumRight := prefix[r] - prefix[l]
            // 减去子问题结果，编码「对手也在最优行动」。
            takeLeft := sumLeft - dp[l+1][r]
            takeRight := sumRight - dp[l][r-1]
            if takeLeft > takeRight {
                dp[l][r] = takeLeft
            } else {
                dp[l][r] = takeRight
            }
        }
    }

    return dp[0][n-1]
}

复杂度分析

  • 时间复杂度：$O(n²)$，每个区间比较两个候选。
  • 空间复杂度：$O(n²)$，保存区间状态。

关键点总结

[!green]

  • 得分来自剩余石子，不是拿走的石子。
  • 子问题换了行动者，所以使用减号。
  • 状态保存从当前区间开始的分差，与过去得分无关。

易错点总结

[!yellow]

  • 加上对手状态：变成双方合作累计收益。
  • 单元素初始化为石子值：最后拿走时实际得到零分。
  • 剩余和仍包含被拿走端点：本轮得分被高估。
  • 先算长区间再算依赖：使用到尚未完成的状态。

相似题目

题目 难度 关联与区别
486. 预测赢家 中等 同样按区间保存当前玩家能领先的最大分差，但本题得分是移除后剩余元素和。
1563. 石子游戏 V 困难 同样用区间和快速计算游戏得分，原题按分割点留下较小一侧，本题只删除左右端点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/90616184
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！