LeetCode 486. 预测赢家

约 5 分钟
文章信息 9 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 华为 微软 亚马逊
标签
数组 动态规划 数学 递归 博弈 极小化极大

题目描述

✅ 486. 预测赢家

image-20260928221913280

image-20260928221913281

题意分析

两名玩家轮流从数组的一端取走一个数，计入自己的得分，直到取完。双方都会让自己的最终得分尽可能高，求玩家 1 能否至少打平。每次只能取两端，所以剩余数字始终构成一个连续区间。

解法：区间 DP 计算最大分差

核心思路

[!blue]

直接记录两人的分数会引入不必要的状态。一个区间的数字总和固定，当前玩家拿得越多，对手就拿得越少，因此最大化自己的得分，等价于最大化「自己的得分减去对手的得分」。已经取走的分数不会影响剩余区间中的最优选择。

定义 dp[left][right]：只考虑剩余区间 nums[left..right]，双方都最优行动时，当前行动者相对另一人能取得的最大分差。这里的当前行动者随回合切换，不固定指玩家 1，分差也允许为负。

当前玩家若取左端，立即得到 nums[left]，随后轮到对手处理 nums[left + 1..right]。子状态 dp[left + 1][right] 是对手相对当前玩家的优势，换回当前玩家的视角必须取反，所以这次选择的最终分差为 nums[left] - dp[left + 1][right]。取右端同理，得到 nums[right] - dp[left][right - 1]。

两端就是全部合法选择，当前玩家选择分差较大的一个；而被减去的子状态已经包含对手的最优回应，因此这个转移同时考虑了双方的最优策略，不需要额外再枚举对手的行动。

只剩一个数时，当前玩家拿走它，对手得到 0，所以 dp[i][i] = nums[i]。从短区间算到长区间，最终 dp[0][n - 1] 才是玩家 1 相对玩家 2 的分差，判断它是否非负即可。

解题步骤

  1. 初始化 dp[i][i] = nums[i]。
  2. 按区间长度从 2 到 n 枚举，再枚举左端点并确定右端点。
  3. 分别计算 nums[left] - dp[left + 1][right] 与 nums[right] - dp[left][right - 1]，将较大值写入当前状态。
  4. 返回 dp[0][n - 1] >= 0，因为平局也算先手获胜。

题目保证数组非空且数字非负。只有一个数时，初始化已经给出答案；所有数字为 0 时最终分差也是 0，应返回成功。

代码实现

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

        for (int idx = 0; idx < n; idx++) {
            dp[idx][idx] = nums[idx];
        }

        for (int len = 2; len <= n; len++) {
            for (int left = 0; left + len - 1 < n; left++) {
                int right = left + len - 1;
                // dp 表示当前玩家相对对手的最大分差，取完后角色交换。
                int takeLeft = nums[left] - dp[left + 1][right];
                int takeRight = nums[right] - dp[left][right - 1];

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

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

func predictTheWinner(nums []int) bool {
    n := len(nums)
    dp := make([][]int, n)
    for idx := 0; idx < n; idx++ {
        dp[idx] = make([]int, n)
        dp[idx][idx] = nums[idx]
    }

    for length := 2; length <= n; length++ {
        for left := 0; left+length-1 < n; left++ {
            right := left + length - 1
            // dp 表示当前玩家相对对手的最大分差，取完后角色交换。
            takeLeft := nums[left] - dp[left+1][right]
            takeRight := nums[right] - dp[left][right-1]
            dp[left][right] = max(takeLeft, takeRight)
        }
    }
    return dp[0][n-1] >= 0
}

func max(first int, second int) int {
    if first > second {
        return first
    }
    return second
}

复杂度分析

  • 时间复杂度：$O(n^2)$，每个区间做常数次运算。
  • 空间复杂度：$O(n^2)$。

关键点总结

[!green]

  • 区间总和固定，最大化自己的得分等价于最大化相对对手的分差。
  • 状态记录当前行动者的优势；轮到对手后，子问题的优势要取反。
  • 依赖来自更短区间，所以按长度递增填表。
  • 最外层的当前行动者是玩家 1，分差非负就满足题目的获胜条件。

易错点总结

[!yellow]

  • dp 不是玩家 1 的固定视角，也不是当前玩家拿到的总分；混淆定义会把转移中的减号写错。
  • 只比较两个端点的大小，会忽略取走端点后给对手留下的局面，不能保证最终得分最大。
  • 忘记初始化 dp[i][i]，会让所有转移从错误基线开始。
  • 分差为负的子区间也必须保留，它表示轮到行动的人处于劣势；不能把负值截成 0。
  • 以 > 0 判断会把平局判负，最终条件必须是 >= 0。

相似题目

题目 难度 关联与区别
877. 石子游戏 中等 同样从两端取石子，原题的偶数堆数和总和条件可推出特殊必胜结论，本题通常需要区间胜负差DP。
1140. 石子游戏 II 中等 同样基于双方最优回应建立状态，原题每轮可取数量还由参数M决定。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/29945168
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！