LeetCode 1563. 石子游戏 V

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 华为
标签
数组 动态规划 数学 博弈

题目描述

✅ 1563. 石子游戏 V

image-20260929085305609

image-20260929085305698

题意分析

每轮由 Alice 把当前石子序列切成左右两个非空连续部分。Bob 丢弃总和较大的一侧，Alice 得到留下部分的总和，并在这一部分继续游戏；两侧总和相等时，Alice 可以选择留下哪侧。

只剩一颗石子时结束，求 Alice 能获得的最大总分。选择切点时既要考虑本轮得分，也要考虑保留区间之后还能得到多少分，不能只贪心选择当前收益最大的切法。

解法：区间动态规划

核心思路

[!blue]

定义 dp[left][right] 为从闭区间 [left, right] 开始游戏，还能获得的最大分数。此前已经得到的分数不会影响当前选择，因此状态只需要两个区间端点。单元素区间无法继续分割，后续得分为 0。

枚举切点 split，把区间分成 [left, split] 和 [split + 1, right]，用前缀和计算 leftSum 与 rightSum。若左侧较小，只能保留左侧，候选收益为 leftSum + dp[left][split]；右侧较小时，候选为 rightSum + dp[split + 1][right]。

两侧总和相等时，本轮得分相同，但两侧的后续最优值可能不同，所以两个候选都要比较。代码用两个独立的 <=、>= 分支，让相等时两边都参与更新，最后在所有切点的合法候选中取最大值。

每次保留下来的区间都严格变短，因此按区间长度递增填表，就能保证转移依赖已经求好。前缀和则让每个切点的两侧总和都能在常数时间得到。

解题步骤

  1. 建立 prefix[i]，表示前 i 颗石子的总和；所有单元素状态 dp[i][i] 保持为 0。
  2. 从长度 2 到 n 枚举区间，再确定左右端点。
  3. 枚举 left <= split < right，保证两侧非空，并通过前缀差计算左右总和。
  4. 对每个允许保留的方向，计算“本轮保留侧总和 + 该侧后续最优值”，更新当前状态。
  5. 返回整个区间的状态 dp[0][n - 1]。

代码实现

class Solution {
    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        int[] prefix = new int[n + 1];

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

        // 状态表示从当前区间开始的后续得分，单元素区间为零。
        int[][] dp = new int[n][n];

        for (int length = 2; length <= n; length++) {
            for (int left = 0; left + length <= n; left++) {
                int right = left + length - 1;

                for (int split = left; split < right; split++) {
                    int leftSum = prefix[split + 1] - prefix[left];
                    int rightSum = prefix[right + 1] - prefix[split + 1];

                    // 保留较小侧，计入本轮分数及该侧后续收益。
                    if (leftSum <= rightSum) {
                        dp[left][right] = Math.max(dp[left][right], leftSum + dp[left][split]);
                    }

                    // 相等时此分支也要执行，两侧后续收益可能不同。
                    if (leftSum >= rightSum) {
                        dp[left][right] =
                                Math.max(dp[left][right], rightSum + dp[split + 1][right]);
                    }
                }
            }
        }

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

func stoneGameV(stoneValue []int) int {
    n := len(stoneValue)
    prefix := make([]int, n+1)
    for i, value := range stoneValue {
        prefix[i+1] = prefix[i] + value
    }

    // 状态表示从当前区间开始的后续得分，单元素区间为零。
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for length := 2; length <= n; length++ {
        for left := 0; left+length <= n; left++ {
            right := left + length - 1
            for split := left; split < right; split++ {
                leftSum := prefix[split+1] - prefix[left]
                rightSum := prefix[right+1] - prefix[split+1]

                // 保留较小侧，计入本轮分数及该侧后续收益。
                if leftSum <= rightSum {
                    dp[left][right] = maxInt(
                        dp[left][right], leftSum+dp[left][split])
                }
                // 相等时此分支也要执行，两侧后续收益可能不同。
                if leftSum >= rightSum {
                    dp[left][right] = maxInt(
                        dp[left][right], rightSum+dp[split+1][right])
                }
            }
        }
    }
    return dp[0][n-1]
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(n³)$，平方数量的区间各枚举切点。
  • 空间复杂度：$O(n²)$，保存区间状态，前缀和另占 $O(n)$。

关键点总结

[!green]

  • 状态是当前区间的后续收益，不是它的元素和，也不包含此前轮次的得分。
  • 保留方向由两侧总和决定，只有相等时才可自由选择。
  • 枚举切点覆盖了 Alice 当前所有合法选择，再接上子区间最优解即可得到整体最优。
  • 按长度填表，让较短的依赖区间先于当前区间完成。

易错点总结

[!yellow]

  • 相等时不能用互斥分支只算一侧，两侧后续分数可能不同。
  • 不能任意保留总和较大的一侧，题目规定它会被丢弃。
  • 切点必须让左右两段都非空，且前缀差的右边界需要加一。
  • 单颗石子的状态是 0，不能再额外加上它的数值；它没有后续可执行的分割操作。

相似题目

题目 难度 关联与区别
486. 预测赢家 中等 同样用区间状态分析游戏，本题保留哪一侧受两侧总和决定，不能直接用任选端点的转移。
1690. 石子游戏 VII 中等 同样需要区间和计算本轮得分，原题删除一端，本题选择分割点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/23928739
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！