LeetCode 877. 石子游戏

约 5 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 腾讯 字节 微软 虾皮
标签
数组 动态规划 数学 博弈 极小化极大

题目描述

✅ 877. 石子游戏

image-20260929000516769

image-20260929000516770

题意分析

两人轮流从剩余石子堆的两端取走一整堆，得分等于拿到的石子数，双方都采用最优策略，判断先手能否获胜。题目保证堆数为偶数、石子总数为奇数，因此不会平局；这两个条件还允许直接证明先手必胜。

解法：区间 DP 计算先手分差

核心思路

[!blue]

每次只能拿两端，剩余部分始终是连续区间。定义 dp[i][j] 为只剩区间 [i, j] 时，当前行动玩家最终得分减去对手得分的最大值。状态不固定代表某个人，正值表示当前玩家能领先，负值表示他即使最优应对也会落后。

若拿左端，先得到 piles[i]，随后对手成为 [i + 1, j] 的行动方。剩余区间中“对手减本方”的最优分差是 dp[i + 1][j]，所以整段中“本方减对手”的分差为 piles[i] - dp[i + 1][j]。拿右端同理，得到 piles[j] - dp[i][j - 1]，当前玩家选较大值。

只剩一堆时，当前玩家全部拿走，故 dp[i][i] = piles[i]。每次转移都依赖少一堆的区间，按区间长度递增计算即可；最终 dp[0][n - 1] > 0 就表示先手获胜。

解题步骤

  1. 创建二维数组 dp，将所有 dp[i][i] 初始化为 piles[i]。
  2. 枚举长度 len = 2..n，再枚举左端 left，得到右端 right = left + len - 1。
  3. 分别计算拿左端、拿右端后的净分差，取最大值写入 dp[left][right]。
  4. 返回完整区间的分差是否大于 0。

代码实现

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            // 单独一堆全部归当前玩家，分差就是这堆数量
            dp[i][i] = piles[i];
        }

        // 短区间先完成，换手后的状态才可读取
        for (int len = 2; len <= n; len++) {
            for (int left = 0; left + len - 1 < n; left++) {
                int right = left + len - 1;

                // 剩余区间优势属于对手，转回当前玩家必须相减
                int takeLeft = piles[left] - dp[left + 1][right];
                int takeRight = piles[right] - dp[left][right - 1];

                dp[left][right] = Math.max(takeLeft, takeRight);
            }
        }

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

func stoneGame(piles []int) bool {
    n := len(piles)
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        // 单独一堆全部归当前玩家，分差就是这堆数量
        dp[i][i] = piles[i]
    }
    // 短区间先完成，换手后的状态才可读取
    for length := 2; length <= n; length++ {
        for left := 0; left+length-1 < n; left++ {
            right := left + length - 1

            // 剩余区间优势属于对手，转回当前玩家必须相减
            takeLeft := piles[left] - dp[left+1][right]
            takeRight := piles[right] - dp[left][right-1]
            if takeLeft > takeRight {
                dp[left][right] = takeLeft
            } else {
                dp[left][right] = takeRight
            }
        }
    }
    return dp[0][n-1] > 0
}

复杂度分析

  • 时间复杂度：$O(n^2)$，其中 n 为堆数；每个区间比较两种决策。
  • 空间复杂度：$O(n^2)$，保存区间状态。

关键点总结

[!green]

  • 状态不是固定某名玩家的总得分，而是当前行动方的分差。
  • 减去剩余区间的分差，正是把对手视角换回当前玩家视角。
  • 区间 DP 不依赖本题的奇偶限制，也可用于一般的两端取数博弈。

解法二：奇偶位置必胜策略

核心思路

[!blue]

按原数组下标，把石子堆分成偶数位置和奇数位置两组。堆数为偶数，最初两端的下标奇偶性不同，先手可以选择想要的一组。

先手拿走选定奇偶性的一端后，剩余区间长度为奇数，两端都属于另一组，对手无论拿哪端都只能拿另一组。对手拿完后，区间又变为偶数长度，两端奇偶性不同，先手仍能拿到自己选定的一组。重复这一过程，先手可以拿完指定组的全部石子。

石子总数为奇数，两组总和不可能相等。先手选择总和较大的一组就一定获胜，因此题目约束内始终返回 true。接口只问是否能赢，无需真正计算两组总和或模拟取石过程。

解题步骤

  1. 利用偶数堆证明先手可以始终拿到指定奇偶位置的堆。
  2. 利用奇数总和保证有一组严格更大，直接返回 true。

代码实现

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

func stoneGame(piles []int) bool {
    return true
}

复杂度分析

  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 奇偶位置始终按原数组下标划分，取走端点不会改变分组。
  • 偶数堆保证能控制一整组，奇数总和保证两组之间存在严格大小关系。

易错点总结

[!yellow]

  • 拿到石头后把对手优势相加，会错误地把对方收益算给自己。
  • 省略单点初值，后续区间全部读到错误基础。
  • 每次只拿较大端点，没有考虑留给对手的选择。
  • 直接返回 true 依赖本题的两个奇偶条件，不能照搬到一般的两端取数题。

相似题目

题目 难度 关联与区别
486. 预测赢家 中等 本题特殊的偶数堆与总和条件可给出必胜策略，原题一般区间取数需要计算胜负差。
1140. 石子游戏 II 中等 原题每次可取数量还受动态M影响，本题固定从两端取一堆，状态结构不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/97667882
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！