文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 示例测试及结果
- 再举一个直观点的例子
- 时间复杂度
- 空间复杂度
- 总结
摘要
这道题表面看起来像是个简单的博弈问题，但真正写起来，很多人会直接被「状态爆炸」劝退。maxChoosableInteger最大能到 20，看似不大，但所有组合一算，状态数量直接飙到百万级。
这类题非常典型：
规则简单 + 最优策略 + 不能贪心 + 需要记忆化搜索。
如果你最近在刷博弈类、状态压缩、DFS + Memo 的题，这道题几乎是绕不开的一关。本文会一步一步拆解思路，并用 Swift 给出一份可运行、好理解的实现。
描述
游戏规则可以简单总结成几句话：
- 有一个公共数字池，数字范围是
1 ~ maxChoosableInteger - 两个玩家轮流选数
- 每个数字只能用一次
- 选中的数字会累加到当前总和
- 谁先让累计和达到或超过
desiredTotal，谁就赢 - 两个玩家都足够聪明，永远走最优解
问题是：
先手玩家，是否一定能赢？
这里有几个关键点很容易被忽略：
- 这是一个典型的「零和博弈」
- 玩家不会随机选，而是“我选了你会怎么反制”
- 不能重复选数，意味着状态不仅和“当前和”有关，还和“哪些数已经用过”有关
这就直接决定了：
贪心是行不通的，暴力 DFS 会超时，必须配合记忆化。
题解答案
核心思路一句话总结：
把“当前还能不能赢”这个问题，抽象成一个函数，用「已经选过的数字集合」作为状态，用 DFS + 记忆化搜索判断是否存在一个必胜选择。
几个重要剪枝先说清楚：
- 如果
desiredTotal <= 0，先手啥都不选就已经赢了，直接返回true - 如果
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的情况下，配合记忆化是完全能跑过的。
空间复杂度
主要消耗在两个地方：
- 记忆化哈希表，最多存
2^n个状态 - DFS 递归栈，深度最多
n
所以空间复杂度是：
O(2^n)这是这类博弈 + 状态压缩题的正常代价。
总结
这道题非常适合用来练三件事：
- 如何把「博弈问题」抽象成递归状态
- 如何用 bitmask 表示“选择过哪些数”
- 如何用记忆化避免指数级重复计算
