LeetCode 486. 预测赢家

2026-01-26 HGNULB 约 5 分钟

文章信息 9 个分类 7 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动微软华为亚马逊

题目描述

✅ 486. 预测赢家

题意分析

给定一个非负整数数组，两名玩家轮流从数组的两端取走一个数并计入自己的总分，先手先取，数组取空时游戏结束。要求判断：在双方都采取最优策略的前提下，先手最终得分是否不低于后手。

「不低于」这三个字要抠清楚：平局也算先手赢，所以判定条件是大于等于而不是严格大于。

「双方都最优」是另一个必须精确理解的信号。它不是「双方都贪心地拿更大的那一端」，而是「双方都会为自己的最终总分做全局最优决策」。对手同样聪明，意味着我这一步的收益必须扣掉对手在剩余局面里能拿到的最优结果——这是所有博弈题的共同结构。

约束里的关键信号是「只能从两端取」。这决定了任意时刻剩下的都是原数组的一段连续区间，局面可以被一对下标 (i, j) 完整描述，状态空间只有 $O(n^2)$ 个，规模可控。

边界包括：数组只有一个元素时先手直接拿走必赢；数组长度为偶数时先手可以用「全取奇数位或全取偶数位」的策略保证不输，但题目并不保证长度为偶数，因此不能靠这个结论蒙混过关；元素可能为 0，所以分差恰好为 0 的平局是真实存在的情况。

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

核心思路

暴力枚举两端选择会产生 $2^n$ 条路径。只记录双方绝对得分也会让状态冗余；真正影响胜负的是分差。

定义 dp[i][j]：面对 nums[i..j] 且轮到当前玩家时，当前玩家在双方最优策略下能取得的最大净胜分。它不绑定具体玩家，取完一个数后视角自动切换：

取左端后的净胜分为 nums[i] - dp[i + 1][j]；

取右端后的净胜分为 nums[j] - dp[i][j - 1]。

因此 dp[i][j] 取两者最大值。减号表示子区间中的优势属于对手，正是我的损失。单元素区间的净胜分就是该元素；按区间长度递增填表，最终 dp[0][n - 1] >= 0 表示先手至少打平。

解题步骤

初始化 dp[i][i] = nums[i]。

按区间长度从 2 到 n 枚举，再枚举左端点并确定右端点。

计算取左、取右后的净胜分，写入二者最大值。

返回 dp[0][n - 1] >= 0，因为平局也算先手获胜。

对 [1,5,2]，长度为 2 的区间净胜分分别是 4、3，整个区间为 max(1 - 3, 2 - 4) = -2，先手必败。对 [1,5,233,7]，整个区间净胜分为 222，先手可获胜。

代码实现

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)$；可用一维滚动数组压缩到 $O(n)$。

关键点总结

状态记录当前行动者的净胜分，无需额外记录玩家身份和两人的总分。

转移中的减号完成视角切换：子区间的当前玩家就是本轮对手。

依赖来自更短区间，所以按长度递增填表。

最终条件必须是 >= 0；若数组长度为偶数，还可用奇偶下标策略证明先手不败。

易错点总结

将减号写成加号，相当于把对手得分也计入自己；[1,5,2] 会被误判。

每轮贪心取较大端点不保证全局最优，[1,5,233,7] 是反例。

忘记初始化 dp[i][i]，会让所有转移从错误基线开始。

以 > 0 判断会把平局判负，例如 [1,1]。

相似题目

题目	难度	考察点
877. 石子游戏	中等	偶数长度下的必胜结论
1690. 石子游戏 VII	中等	前缀和配合两端取数的博弈
312. 戳气球	困难	逆向枚举最后戳破的气球
1000. 合并石头的最低成本	困难	按 K 分组的区间合并与整除性
887. 鸡蛋掉落	困难	最坏情况最优化与二分优化
面试题 08.14. 布尔运算	中等	按运算符切分区间并计数方案