LeetCode 464 我能赢吗

摘要

这道题表面看起来像是个简单的博弈问题，但真正写起来，很多人会直接被「状态爆炸」劝退。
maxChoosableInteger最大能到 20，看似不大，但所有组合一算，状态数量直接飙到百万级。

这类题非常典型：
规则简单 + 最优策略 + 不能贪心 + 需要记忆化搜索。

如果你最近在刷博弈类、状态压缩、DFS + Memo 的题，这道题几乎是绕不开的一关。本文会一步一步拆解思路，并用 Swift 给出一份可运行、好理解的实现。

描述

游戏规则可以简单总结成几句话：

• 有一个公共数字池，数字范围是1 ~ maxChoosableInteger
• 两个玩家轮流选数
• 每个数字只能用一次
• 选中的数字会累加到当前总和
• 谁先让累计和达到或超过desiredTotal，谁就赢
• 两个玩家都足够聪明，永远走最优解

问题是：
先手玩家，是否一定能赢？

这里有几个关键点很容易被忽略：

1. 这是一个典型的「零和博弈」
2. 玩家不会随机选，而是“我选了你会怎么反制”
3. 不能重复选数，意味着状态不仅和“当前和”有关，还和“哪些数已经用过”有关

这就直接决定了：
贪心是行不通的，暴力 DFS 会超时，必须配合记忆化。

题解答案

核心思路一句话总结：

把“当前还能不能赢”这个问题，抽象成一个函数，用「已经选过的数字集合」作为状态，用 DFS + 记忆化搜索判断是否存在一个必胜选择。

几个重要剪枝先说清楚：

1. 如果desiredTotal <= 0，先手啥都不选就已经赢了，直接返回true
2. 如果1 + 2 + ... + maxChoosableInteger < desiredTotal
   那无论怎么选，总和都达不到目标，先手必输

真正的博弈逻辑是：

• 当前玩家尝试选择一个还没用过的数字i
• 如果i >= 剩余目标，当前玩家立刻赢
• 否则，把这个数标记为已使用，递归判断对手是否会输
• 只要存在一个选择，能让对手输，那当前玩家就是稳赢

题解代码分析

下面是完整 Swift 实现，支持直接运行测试。

classSolution{funccanIWin(_maxChoosableInteger:Int,_desiredTotal:Int)->Bool{// 特殊情况：目标本身 <= 0，先手直接赢ifdesiredTotal<=0{returntrue}// 所有数加起来都不够，必输letmaxSum=(1+maxChoosableInteger)*maxChoosableInteger/2ifmaxSum<desiredTotal{returnfalse}varmemo=[Int:Bool]()returndfs(usedMask:0,remaining:desiredTotal,maxNum:maxChoosableInteger,memo:&memo)}privatefuncdfs(usedMask:Int,remaining:Int,maxNum:Int,memo:inout[Int:Bool])->Bool{// 如果这个状态已经算过，直接返回ifletcached=memo[usedMask]{returncached}// 尝试选择每一个还没用过的数字foriin1...maxNum{letbit=1<<(i-1)if(usedMask&bit)!=0{continue}// 如果当前选 i 就能赢，直接返回 trueifi>=remaining{memo[usedMask]=truereturntrue}// 否则，看对手在新状态下是否会输letnextMask=usedMask|bitletopponentWin=dfs(usedMask:nextMask,remaining:remaining-i,maxNum:maxNum,memo:&memo)// 对手输，说明我赢if!opponentWin{memo[usedMask]=truereturntrue}}// 所有选择都会让对手赢，那我必输memo[usedMask]=falsereturnfalse}}

示例测试及结果

我们用题目里的例子来跑一跑。

letsolution=Solution()print(solution.canIWin(10,11))// falseprint(solution.canIWin(10,0))// trueprint(solution.canIWin(10,1))// true

输出结果：

false true true

结果和题目给的一致。

再举一个直观点的例子

print(solution.canIWin(5,6))

解释一下：

• 可选数字是 1~5
• 如果先手选 1，对手选 5，直接赢
• 如果先手选 2，对手选 4，也能赢
• 无论先手怎么走，都挡不住对手

结果自然是false。

时间复杂度

状态的核心是usedMask，它是一个最多 20 位的二进制数。

• 状态数量最多是2^20 ≈ 1,048,576
• 每个状态最多遍历maxChoosableInteger次

所以时间复杂度可以近似认为是：

O(2^n * n)

在题目限制n <= 20的情况下，配合记忆化是完全能跑过的。

空间复杂度

主要消耗在两个地方：

1. 记忆化哈希表，最多存2^n个状态
2. DFS 递归栈，深度最多n

所以空间复杂度是：

O(2^n)

这是这类博弈 + 状态压缩题的正常代价。

总结

这道题非常适合用来练三件事：

1. 如何把「博弈问题」抽象成递归状态
2. 如何用 bitmask 表示“选择过哪些数”
3. 如何用记忆化避免指数级重复计算