LeetCode 486. 预测赢家
字数 2851 2025-12-12 23:50:05

LeetCode 486. 预测赢家

题目描述

给定一个非负整数数组 nums。两位玩家（玩家1先手，玩家2后手）轮流从数组的任意一端（即 nums[0] 或 nums[nums.length - 1]）取一个数字。每次取数后，该数字会从数组中移除。游戏持续到数组中的所有数字都被取完为止。

最终获得分数总和（即所取数字之和）更高的玩家获胜。如果两位玩家的分数相等，则玩家1仍被视为获胜者。

假设两位玩家都采用最优策略进行游戏。如果玩家1能够获胜（包括平局），则返回 true，否则返回 false。

示例 1
输入：nums = [1, 5, 2]
输出：false
解释：玩家1先手，可以选择取1或2。

  • 如果取1，则数组变为[5, 2]。玩家2（最优策略）会取5。之后玩家1只能取2。总分：玩家1 = 1+2=3， 玩家2 = 5。玩家2获胜。
  • 如果取2，数组变为[1, 5]。玩家2会取5。之后玩家1只能取1。总分：玩家1 = 2+1=3， 玩家2 = 5。玩家2获胜。
    所以，玩家1无论如何都会输，返回false。

示例 2
输入：nums = [1, 5, 233, 7]
输出：true
解释：玩家1先手，取1。数组变为[5, 233, 7]。玩家2必须从5或7中选，他（最优策略）会取7。数组变为[5, 233]。玩家1取233。数组变为[5]。玩家2取5。总分：玩家1 = 1+233=234，玩家2 = 7+5=12。玩家1获胜。

解题过程循序渐进讲解

这个问题是一个典型的零和博弈问题。在双方都采取最优策略的情况下，我们可以通过计算“分数差”来判定先手玩家（玩家1）的胜负。我们可以定义一个函数，用于计算在某个子数组上进行游戏时，当前行动玩家能比对方玩家多拿多少分。

第一步：定义状态与递归函数

我们定义 dfs(i, j) 表示：当数组剩下从索引 i 到 j (i <= j) 的子数组时，当前要行动的玩家（注意，不一定是玩家1），采取最优策略，最终能比对方玩家多获得多少分数。

例如，在初始状态 dfs(0, n-1) 中，当前行动的玩家是玩家1，如果这个函数值 >= 0，就说明玩家1至少不会输（分数差大于等于0）。

第二步：推导状态转移方程（核心思路）

现在轮到当前玩家行动，他面临一个子数组 nums[i...j]。他有两个选择：

  1. 拿走左端的数字 nums[i]。那么，剩下的子数组是 nums[i+1...j]，轮到对方玩家行动。当前玩家通过这个操作，能立刻获得 nums[i] 分，并且在后续的游戏中，对方玩家会在子数组 [i+1, j] 上努力扩大他相对于当前玩家的分数差。这个差值，从当前玩家的视角看，是 -dfs(i+1, j)。所以，选择左端能为当前玩家带来的净分数差优势是：
    nums[i] - dfs(i+1, j)
  2. 拿走右端的数字 nums[j]。同理，这个选择带来的净分数差优势是：
    nums[j] - dfs(i, j-1)

当前玩家是聪明的，他会选择对自己最有利（即让分数差最大化）的操作。因此，状态转移方程为：
dfs(i, j) = max(nums[i] - dfs(i+1, j), nums[j] - dfs(i, j-1))

第三步：确定递归边界（Base Case）

当子数组只有一个数字时，即 i == j。当前玩家只能取这个数字，对方得0分。所以当前玩家能比对方多获得的分数就是 nums[i]。
即：dfs(i, i) = nums[i]

第四步：从递归到记忆化搜索

直接使用上面的递归函数会有大量的重复计算。我们可以用一个二维数组 memo[i][j] 来记录已经计算过的 dfs(i, j) 的结果，这就是记忆化搜索（或称自顶向下的动态规划）。

  • 初始化 memo 为一个特殊值（如 None），表示未计算。
  • 在递归函数中，先检查 memo[i][j] 是否已计算，是则直接返回。
  • 否则，根据递推公式计算，并将结果存入 memo[i][j] 后再返回。

第五步：示例推导（以 nums = [1, 5, 2] 为例）

我们来模拟一下记忆化搜索的计算过程，以验证 dfs(0, 2) < 0。

  1. 计算 dfs(0, 2)：

    • 选择左端1：1 - dfs(1, 2)
    • 选择右端2：2 - dfs(0, 1)
    • dfs(0, 2) = max(1 - dfs(1, 2), 2 - dfs(0, 1)) (结果待定)

  2. 需要先计算 dfs(1, 2) (子数组[5, 2])：

    • 选择左端5：5 - dfs(2, 2)
    • 选择右端2：2 - dfs(1, 1)
    • 先计算 dfs(2,2)=2, dfs(1,1)=5
    • 所以 dfs(1,2) = max(5-2, 2-5) = max(3, -3) = 3

  3. 再计算 dfs(0, 1) (子数组[1, 5])：

    • 选择左端1：1 - dfs(1, 1)
    • 选择右端5：5 - dfs(0, 0)
    • 先计算 dfs(1,1)=5, dfs(0,0)=1
    • 所以 dfs(0,1) = max(1-5, 5-1) = max(-4, 4) = 4

  4. 代回第一步：
    dfs(0,2) = max(1 - 3, 2 - 4) = max(-2, -2) = -2

dfs(0,2) = -2 < 0，这意味着在初始状态下，作为当前玩家的玩家1，即使采取最优策略，最终也会比玩家2少2分。所以玩家1会输，函数返回 false。

第六步：最终实现与复杂度

我们可以用二维数组 dp[i][j] 来实现自底向上的动态规划，其含义与 memo[i][j] 完全相同。

  • 初始化：dp[i][i] = nums[i] （对角线，只有一个数字的情况）。
  • 我们需要按子数组长度 len 从2到n进行递推。因为计算 dp[i][j] 需要先知道 dp[i+1][j] 和 dp[i][j-1]，即其左边和下边的值。按长度从小到大的顺序可以满足。
  • 最终结果：判断 dp[0][n-1] >= 0。

时间复杂度：O(n²)，因为我们需要填充一个 n x n 的二维DP表。
空间复杂度：O(n²)。可以优化到O(n)，但理解核心思想时，二维数组更直观。

总结一下关键点：

  1. 定义 dfs(i,j) 为当前玩家在子数组 [i,j] 上能获得的相对分数优势（当前玩家分数 - 对方玩家分数）。
  2. 状态转移基于“当前选择获得的分数”减去“对方在剩余部分获得的相对优势”。
  3. 最终判断初始状态的相对优势 dfs(0, n-1) 是否非负。
LeetCode 486. 预测赢家 题目描述 给定一个非负整数数组 nums 。两位玩家（玩家1先手，玩家2后手）轮流从数组的任意一端（即 nums[0] 或 nums[nums.length - 1] ）取一个数字。每次取数后，该数字会从数组中移除。游戏持续到数组中的所有数字都被取完为止。 最终获得分数总和（即所取数字之和）更高的玩家获胜。如果两位玩家的分数相等，则玩家1仍被视为获胜者。 假设两位玩家都采用 最优策略 进行游戏。如果玩家1能够获胜（包括平局），则返回 true ，否则返回 false 。 示例 1 输入：nums = [ 1, 5, 2 ] 输出：false 解释：玩家1先手，可以选择取1或2。 如果取1，则数组变为[ 5, 2 ]。玩家2（最优策略）会取5。之后玩家1只能取2。总分：玩家1 = 1+2=3， 玩家2 = 5。玩家2获胜。 如果取2，数组变为[ 1, 5 ]。玩家2会取5。之后玩家1只能取1。总分：玩家1 = 2+1=3， 玩家2 = 5。玩家2获胜。 所以，玩家1无论如何都会输，返回false。 示例 2 输入：nums = [ 1, 5, 233, 7 ] 输出：true 解释：玩家1先手，取1。数组变为[ 5, 233, 7]。玩家2必须从5或7中选，他（最优策略）会取7。数组变为[ 5, 233]。玩家1取233。数组变为[ 5 ]。玩家2取5。总分：玩家1 = 1+233=234，玩家2 = 7+5=12。玩家1获胜。 解题过程循序渐进讲解 这个问题是一个典型的 零和博弈 问题。在双方都采取最优策略的情况下，我们可以通过计算“分数差”来判定先手玩家（玩家1）的胜负。我们可以定义一个函数，用于计算在某个 子数组 上进行游戏时， 当前行动玩家 能比 对方玩家 多拿多少分。 第一步：定义状态与递归函数 我们定义 dfs(i, j) 表示：当数组剩下从索引 i 到 j ( i <= j ) 的子数组时， 当前要行动的玩家 （注意，不一定是玩家1），采取最优策略，最终能比 对方玩家 多获得多少分数。 例如，在初始状态 dfs(0, n-1) 中，当前行动的玩家是玩家1，如果这个函数值 >= 0 ，就说明玩家1至少不会输（分数差大于等于0）。 第二步：推导状态转移方程（核心思路） 现在轮到当前玩家行动，他面临一个子数组 nums[i...j] 。他有两个选择： 拿走左端的数字 nums[i] 。那么，剩下的子数组是 nums[i+1...j] ，轮到对方玩家行动。当前玩家通过这个操作，能立刻获得 nums[i] 分，并且在后续的游戏中， 对方玩家 会在子数组 [i+1, j] 上努力扩大他相对于当前玩家的分数差。这个差值，从当前玩家的视角看，是 -dfs(i+1, j) 。所以，选择左端能为当前玩家带来的 净分数差优势 是： nums[i] - dfs(i+1, j) 拿走右端的数字 nums[j] 。同理，这个选择带来的 净分数差优势 是： nums[j] - dfs(i, j-1) 当前玩家是聪明的，他会选择对自己最有利（即让分数差最大化）的操作。因此，状态转移方程为： dfs(i, j) = max(nums[i] - dfs(i+1, j), nums[j] - dfs(i, j-1)) 第三步：确定递归边界（Base Case） 当子数组只有一个数字时，即 i == j 。当前玩家只能取这个数字，对方得0分。所以当前玩家能比对方多获得的分数就是 nums[i] 。 即： dfs(i, i) = nums[i] 第四步：从递归到记忆化搜索 直接使用上面的递归函数会有大量的重复计算。我们可以用一个二维数组 memo[i][j] 来记录已经计算过的 dfs(i, j) 的结果，这就是 记忆化搜索 （或称自顶向下的动态规划）。 初始化 memo 为一个特殊值（如 None ），表示未计算。 在递归函数中，先检查 memo[i][j] 是否已计算，是则直接返回。 否则，根据递推公式计算，并将结果存入 memo[i][j] 后再返回。 第五步：示例推导（以 nums = [ 1, 5, 2] 为例） 我们来模拟一下记忆化搜索的计算过程，以验证 dfs(0, 2) < 0 。 计算 dfs(0, 2) ： 选择左端1： 1 - dfs(1, 2) 选择右端2： 2 - dfs(0, 1) dfs(0, 2) = max(1 - dfs(1, 2), 2 - dfs(0, 1)) (结果待定) 需要先计算 dfs(1, 2) (子数组[ 5, 2 ])： 选择左端5： 5 - dfs(2, 2) 选择右端2： 2 - dfs(1, 1) 先计算 dfs(2,2)=2 , dfs(1,1)=5 所以 dfs(1,2) = max(5-2, 2-5) = max(3, -3) = 3 再计算 dfs(0, 1) (子数组[ 1, 5 ])： 选择左端1： 1 - dfs(1, 1) 选择右端5： 5 - dfs(0, 0) 先计算 dfs(1,1)=5 , dfs(0,0)=1 所以 dfs(0,1) = max(1-5, 5-1) = max(-4, 4) = 4 代回第一步： dfs(0,2) = max(1 - 3, 2 - 4) = max(-2, -2) = -2 dfs(0,2) = -2 < 0 ，这意味着在初始状态下，作为当前玩家的玩家1，即使采取最优策略，最终也会比玩家2 少 2分。所以玩家1会输，函数返回 false 。 第六步：最终实现与复杂度 我们可以用二维数组 dp[i][j] 来实现 自底向上 的动态规划，其含义与 memo[i][j] 完全相同。 初始化： dp[i][i] = nums[i] （对角线，只有一个数字的情况）。 我们需要按 子数组长度 len 从2到n进行递推。因为计算 dp[i][j] 需要先知道 dp[i+1][j] 和 dp[i][j-1] ，即其左边和下边的值。按长度从小到大的顺序可以满足。 最终结果：判断 dp[0][n-1] >= 0 。 时间复杂度 ：O(n²)，因为我们需要填充一个 n x n 的二维DP表。 空间复杂度 ：O(n²)。可以优化到O(n)，但理解核心思想时，二维数组更直观。 总结一下关键点 ： 定义 dfs(i,j) 为 当前玩家 在子数组 [i,j] 上能获得的 相对分数优势 （当前玩家分数 - 对方玩家分数）。 状态转移基于“当前选择获得的分数”减去“对方在剩余部分获得的相对优势”。 最终判断初始状态的相对优势 dfs(0, n-1) 是否非负。