LeetCode 题解工作台
预测赢家
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即， nums[0] 或 nums[nums.length - 1] ），取到的…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $\textit{dfs}(i, j)$，表示从第 个数到第 个数，当前玩家与另一个玩家的得分之差的最大值。那么答案就是 $\textit{dfs}(0, n - 1) \geq 0$。 函数 $\textit{dfs}(i, j)$ 的计算方法如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。
示例 1：
输入：nums = [1,5,2] 输出：false 解释：一开始，玩家 1 可以从 1 和 2 中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 false 。
示例 2：
输入：nums = [1,5,233,7] 输出：true 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。 最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。
提示：
1 <= nums.length <= 200 <= nums[i] <= 107
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从第 个数到第 个数，当前玩家与另一个玩家的得分之差的最大值。那么答案就是 。
函数 的计算方法如下：
- 如果 ，说明当前没有数字了，所以当前玩家没有分数可以拿，差值为 ，即 。
- 否则，当前玩家有两种选择，如果选择第 个数，那么当前玩家与另一个玩家的得分之差为 ；如果选择第 个数，那么当前玩家与另一个玩家的得分之差为 。当前玩家会选择两种情况中差值较大的情况，也就是说 。
最后，我们只需要判断 即可。
为了避免重复计算，我们可以使用记忆化搜索的方法，用一个数组 记录所有的 的值，当函数再次被调用到时，我们可以直接从 中取出答案而不需要重新计算。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def predictTheWinner(self, nums: List[int]) -> bool:
@cache
def dfs(i: int, j: int) -> int:
if i > j:
return 0
return max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1))
return dfs(0, len(nums) - 1) >= 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate explain the optimal substructure and state transition of this problem?
- question_mark
Does the candidate properly implement dynamic programming and memoization techniques?
- question_mark
Can the candidate recognize the need for recursion and optimize with memoization?
常见陷阱
外企场景- error
Failing to implement the correct state transition for subarrays, leading to incorrect predictions of the winner.
- error
Not using memoization properly, causing unnecessary recomputation and inefficient performance.
- error
Overlooking the need to handle both player choices optimally, potentially assuming one player will always make a bad choice.
进阶变体
外企场景- arrow_right_alt
What if the array contains negative numbers? How would the strategy change?
- arrow_right_alt
Can the solution be optimized further in terms of space complexity?
- arrow_right_alt
What happens if Player 1 and Player 2 can only pick the same number on each turn?