外包离职后，把核心代码上传到GitHub，项目组已退场，大概率找不到人了

我昨天晚上十一点多在公司楼下抽烟，手机上随手点开这题，第一眼很多人都会这么想： “那不就是轮流抢数字嘛，我挑大的就好了？”。

结果一写就发现不对劲：

• 数字是一次性用掉的，你拿了 10 就没 10 了
• 你现在贪大，可能给对面留下一个刚好能凑到目标的局面
• 而且题目数据范围：maxChoosableInteger ≤ 20，这就有点“暗示你用状态压缩”的味道了

暴力想法是有的：把所有没拿过的数字枚举一遍，每种拿法都递归下去，看是不是能赢。问题是，如果不记忆化，这棵搜索树会爆炸。

几个关键小结论（真的很重要）

这题有两个非常实用的剪枝，面试的时候顺着这个路子说，面试官一般就知道你会做了：

1. 总和都不够，直接 false所有数加起来小于 desiredTotal，那不管谁怎么玩，都到不了目标，肯定没人能赢：

   int sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
   if (sum < desiredTotal) returnfalse;
   

2. 当前一手就能赢，直接 true在某个局面下，如果还有一个没用过的数字 i，满足 i >= remain（remain 是离目标还差多少），那当前这个人直接拿 i 就结束游戏了，这个状态就是必胜状态。

接下来就是：怎么表示“当前已经用了哪些数字”，以及怎么记忆化。

状态怎么存？位掩码这玩意就派上用场了

因为 maxChoosableInteger ≤ 20，我们可以用一个 int 的二进制位来表示每个数字用没用：

• 0 号 bit 表示 1 用没用
• 1 号 bit 表示 2 用没用
• …
• 第 (i-1) 位表示数字 i 是否已经被选过

某一位是 1，表示这个数字已经拿过了；是 0，表示还可以选。 这样整个“局面”就可以用一个整数 state 表示。

为啥要这样干？ 因为我们递归的时候，每次面对的，其实就是“当前剩哪些数字 + 还差多少总和”，而剩哪些数字完全可以用 state 表示，然后我们就可以用一个 Map<Integer, Boolean> 或 Boolean[] memo 来记忆化：

• memo[state] == true 表示：在这个状态下，当前轮到的人是必胜的
• memo[state] == false 表示：当前轮到的人怎么下都赢不了（对手太聪明）

核心递归逻辑其实就一句话

从当前状态出发，只要你能找到一个数字 i：

• i 还没被用过

• 如果你拿了 i，要么：

• 直接赢（i >= remain）
• 要么拿完后，对手的局面是必败的

那你就是必胜的。

翻成伪代码就是：

对所有还能选的 i：  如果 i >= remain，当前玩家赢  否则，看下一步状态 nextState 对手是不是必败  如果有一个 i 能让对手必败，那当前就是必胜

如果所有 i 都试完了：要么拿了也赢不了，要么拿了之后对手都是必胜，那你就完蛋了，这个状态就是失败状态。

上点 Java 代码，别太花里胡哨的那种

publicclassSolution{

publicbooleancanIWin(int maxChoosableInteger, int desiredTotal){
// 剪枝一：总和都不够，谁也赢不了
int sum = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
if (sum < desiredTotal) {
returnfalse;
        }
// 剪枝二：目标 <= 最大数，你先手直接拿最大那个就赢
if (desiredTotal <= maxChoosableInteger) {
returntrue;
        }

// 记忆化：state -> 当前玩家在这个状态下是否必胜
        Boolean[] memo = new Boolean[1 << maxChoosableInteger];
return dfs(maxChoosableInteger, desiredTotal, 0, memo);
    }

/**
     * @param max    最大可选数字
     * @param remain 距离目标还差多少
     * @param state  已选择数字的状态，二进制位表示
     * @param memo   记忆化数组
     */
privatebooleandfs(int max, int remain, int state, Boolean[] memo){
if (memo[state] != null) {
return memo[state];
        }

// 从 1 到 max 尝试每一个没用过的数字
for (int i = 1; i <= max; i++) {
int bit = 1 << (i - 1);
// 已经用过就跳过
if ((state & bit) != 0) {
continue;
            }

// 1. 直接拿这个数就能达到或超过目标，当前玩家立刻获胜
if (i >= remain) {
                memo[state] = true;
returntrue;
            }

// 2. 否则，假装我拿了 i，轮到对手
int nextState = state | bit;
boolean opponentWin = dfs(max, remain - i, nextState, memo);

// 只要有一种选择能让对手在之后的状态中“赢不了”，
// 那当前就是必胜状态
if (!opponentWin) {
                memo[state] = true;
returntrue;
            }
        }

// 所有选择尝试完，都不能让对手陷入必败，那我就是必败
        memo[state] = false;
returnfalse;
    }
}

这个写法有几个点面试时可以顺带嘴上提一嘴：

• 用 Boolean[] 而不是 boolean[]，因为我们需要三态：null / true / false，null 表示没算过
• 状态数量最多 2^20 ≈ 100w，dfs + 记忆化在这个规模是完全扛得住的
• 搜索顺序无所谓，只要逻辑是“有没有一种选择能让对手必败”，就行

最后随口唠一句

这题本质上就是一个“带记忆化的博弈搜索 + bitmask 压缩状态”，思路一旦通了，你会发现很多类似的“我能赢吗”“先手后手谁有优势”的题，套路都差不多。

行了，不唠了，我去给我们组那个小李解释为啥他的 bit 掩码总写反了…