LeetCode 题解工作台
我能赢吗
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。 如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？ 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们首先判断可以选择的所有整数的和是否小于目标值，如果是，说明无论如何都无法赢，直接返回 `false`。 然后，我们设计一个函数 $\textit{dfs}(mask, s)$，其中 `mask` 表示当前已选择的整数的状态，`s` 表示当前的累计和。函数返回值为当前玩家是否能赢。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
示例 1：
输入：maxChoosableInteger = 10, desiredTotal = 11 输出：false 解释： 无论第一个玩家选择哪个整数，他都会失败。 第一个玩家可以选择从 1 到 10 的整数。 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利. 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
示例 2:
输入：maxChoosableInteger = 10, desiredTotal = 0 输出：true
示例 3:
输入：maxChoosableInteger = 10, desiredTotal = 1 输出：true
提示:
1 <= maxChoosableInteger <= 200 <= desiredTotal <= 300
解题思路
方法一：状态压缩 + 记忆化搜索
我们首先判断可以选择的所有整数的和是否小于目标值，如果是，说明无论如何都无法赢，直接返回 false。
然后，我们设计一个函数 ，其中 mask 表示当前已选择的整数的状态，s 表示当前的累计和。函数返回值为当前玩家是否能赢。
函数 的执行过程如下：
我们遍历 到 中的每个整数 ，如果 还没有被选择，我们可以选择 ，如果选择 后的累计和 大于等于目标值 desiredTotal，或者对手选择 后的结果是输的，那么当前玩家就是赢的，返回 true。
如果没有任何一个选择能让当前玩家赢，那么当前玩家就是输的，返回 false。
为了避免重复计算，我们使用一个哈希表 f 记录已经计算过的状态，键为 mask，值为当前玩家是否能赢。
时间复杂度 ，空间复杂度 。其中 是 maxChoosableInteger。
class Solution:
def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
@cache
def dfs(mask: int, s: int) -> bool:
for i in range(1, maxChoosableInteger + 1):
if mask >> i & 1 ^ 1:
if s + i >= desiredTotal or not dfs(mask | 1 << i, s + i):
return True
return False
if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:
return False
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^N * N) where N is maxChoosableInteger, as each state can have N choices and there are 2^N possible bitmask states. Space complexity is O(2^N) for memoization of all bitmask states. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Watch for exponential state space and propose memoization with bitmasking.
- question_mark
Ask if the player can immediately determine a win based on total sum constraints.
- question_mark
Clarify turn order and enforce choosing only unused numbers to avoid incorrect DP states.
常见陷阱
外企场景- error
Failing to represent used numbers properly, leading to revisiting the same states multiple times.
- error
Ignoring the case where desiredTotal is zero or negative and returning incorrect output.
- error
Not checking if the total sum of all numbers is less than desiredTotal, causing unnecessary computation.
进阶变体
外企场景- arrow_right_alt
Modify the range of numbers or desired total and observe how the DP states scale with larger bitmasks.
- arrow_right_alt
Allow repeated picks of numbers to analyze the change in state transition logic.
- arrow_right_alt
Consider different winning thresholds for multi-player versions and extend the bitmask DP to more players.