大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

数字池中有一堆数字 464. 我能赢吗 - 图1，两个人轮流「不放回」地从这些数字中拿一个数字。

当某个人抽到一个数字 464. 我能赢吗 - 图2后，两个人已抽取的数字的累加和 $>= desiredTotal$，那么此时的人就赢了。

问，先手是否必赢？

注意：与464. 我能赢吗 - 图3比较的，不是「各自」手里的数字之和，而是两个人已抽取的数字都加在一起的和。

以示例一 maxChoosableInteger = 10, desiredTotal = 11为例，解释一下游戏规则。

你会发现，无论先手选择什么数字，先手都必输。因此返回 false。

当 maxChoosableInteger = 10, desiredTotal = 1时，无论如何都是先手赢，因此返回 false。

解题方法

分析

博弈问题，都会假设两个游戏的玩家是聪明的，两个人都会「每次选择前，分析后续所有可能的结果」。

当选择一种方案后，可以让自己稳赢的时候，一定会选择这种方案；当无论怎么选都必输，才不情愿地选择某一个方案。

下象棋时，有「走一步，看三步」的说法。这题更狠，是「走一步，看到底」，选择最有利的方案。

这道题是没有任何规律的，玩家在做选择时，都只能穷举所有的可行的方案，选择最优解。

游戏的规则是：两人轮流在同一个「公共整数池」中拿数字，而且都把「已选择的数字」放在一起求和。

刚开始时，玩家 464. 我能赢吗 - 图4是先手；但在 464. 我能赢吗 - 图5拿走数字完成，轮到玩家 464. 我能赢吗 - 图6时，他可以认为自己是「剩下的这个局面」中的先手。

也就是说，当轮到自己选择的时候，自己就是先手，对方就是后手。

进一步，我们完全可以抛掉「先后手」这个概念，直接变成：「在当前局面下，当前做选择的玩家一定能赢吗？」

这就抽象成了一个「递归」问题：

  • 递归函数定义：在当前局面下，当前做选择的玩家一定能赢吗？
  • 输入：当前局面，包括可选的「公共整数池」，「已选择的数字」之和，desiredTotal。
  • 输出：当前做选择的玩家一定能赢吗？
  • 递归的产生：假如当前玩家从「公共整数池」中选择了数字 $x$，那么当下一步对方在新局面做选择的时候是否一定输。

关于「递归的产生」这里多解释一下。

  • 如果当前做选择的玩家在「公共整数池」中选择 $x$，如果选择了464. 我能赢吗 - 图7之后，让对手一定会输，那么当前玩家一定赢。
  • 如果当前的玩家把「公共整数池」全部遍历判断了，但无论选择哪个数字，对手都一定赢，那么当前玩家就一定输。

应该挺好理解吧。

怎么判断当前玩家能「赢」呢？

当前玩家选择了 464. 我能赢吗 - 图8以后，使得「已选择的数字」之和 464. 我能赢吗 - 图9，那么当前玩家就赢了。

据此，我们可以写出第一版代码如下。

  1. class Solution {
  2. public:
  3.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
  4.         // 候选集，「公共整数池」
  5.         unordered_set<int> choosable;
  6.         for (int i = 1; i <= maxChoosableInteger; ++i) {
  7.             choosable.insert(i);
  8.         }
  9.         // 判断当前做选择的玩家（先手），是否一定赢
  10.         return dfs(choosable, 0, maxChoosableInteger, desiredTotal);
  11.     }
  13.     // 当前做选择的玩家是否一定赢
  14.     bool dfs(unordered_set<int>& choosable, int sum, int maxChoosableInteger, int desiredTotal) {
  15.         // 遍历可选择的公共整数
  16.         for (int x : choosable) {
  17.             // 如果选择了 x 以后，大于等于了 desiredTotal，当前玩家赢
  18.             if (sum + x >= desiredTotal) {
  19.                 return true;
  20.             }
  21.             // 改变「公共整数池」
  22.             // 为了避免影响当前的 choosable，因此复制了一份并擦出掉 x，传给对手
  23.             unordered_set<int> choosable_copy = choosable;
  24.             choosable_copy.erase(x);
  25.             // 当前玩家选择了 x 以后，判断对方玩家一定输吗？
  26.             if (!dfs(choosable_copy, sum + x, maxChoosableInteger, desiredTotal)) {
  27.                 return true;
  28.             }
  29.         }
  30.         return false;
  31.     }
  33. };

这个代码提交会超时，但是基本思路都有了，只需要再优化一下就行。

改进一：使用整型数字，标识「公共整数池」的使用情况

在上面的代码中，我是用的是 464. 我能赢吗 - 图10标记当前玩家可选的「公共整数池」。效率不是很高，因为其中需要保存 464. 我能赢吗 - 图11个数字，并且还要拷贝。

可以使用一个 $int$ 型整数 464. 我能赢吗 - 图12标记整个「公共整数池」的使用情况。

这么 6？

首先，一个 $int$ 型整数的二进制表示中有 $32$ 位，我们令它从右向左数的第 464. 我能赢吗 - 图13位（从 $0$ 开始数）代表「公共整数池」中的整数464. 我能赢吗 - 图14是否在游戏中已经使用过。

  • 比如， 464. 我能赢吗 - 图15，二进制是 464. 我能赢吗 - 图16，表示「公共整数池」中所有数字都没被使用过。
  • 比如， 464. 我能赢吗 - 图17，二进制是 464. 我能赢吗 - 图18，表示「公共整数池」中的整数 464. 我能赢吗 - 图19已经被用过了，以后的回合中都不可以再用464. 我能赢吗 - 图20了。
  • 比如， 464. 我能赢吗 - 图21，二进制是 464. 我能赢吗 - 图22，表示「公共整数池」中的整数 464. 我能赢吗 - 图23和整数 464. 我能赢吗 - 图24已经被用过了，以后的回合中都不可以再用 464. 我能赢吗 - 图25和 464. 我能赢吗 - 图26了。

为什么可以想到使用 464. 我能赢吗 - 图27型整数标记状态的呢？

  1. 范围可以，题目说 1 <= maxChoosableInteger <= 20，也就是不超过464. 我能赢吗 - 图28的 $32$ 位
  2. 「公共整数池」中的所有数字是连续的，也就是从 464. 我能赢吗 - 图29 到 464. 我能赢吗 - 图30，不重复。

标记「公共整数池」的所有数字，原来使用的是 464. 我能赢吗 - 图31，现在使用的是 464. 我能赢吗 - 图32，节省了很多内存。

下面的代码中使用位运算，判断 464. 我能赢吗 - 图33的第 464. 我能赢吗 - 图34位是否是 464. 我能赢吗 - 图35；每次判断下一个玩家的时候，也需要将已经使用过的 464. 我能赢吗 - 图36的第 464. 我能赢吗 - 图37位，置为 1。

改进后的代码如下：

  1. class Solution {
  2. public:
  3.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
  4.         // 判断当前做选择的玩家（先手），是否一定赢
  5.         // 开始时，state = 0，表示「公共整数集」中的所有数字都未被使用过
  6.         return dfs(0, 0, maxChoosableInteger, desiredTotal);
  7.     }
  9.     // 当前做选择的玩家是否一定赢
  10.     bool dfs(int state, int sum, int maxChoosableInteger, int desiredTotal) {
  11.         // 遍历可选择的公共整数
  12.         for (int x = 1; x <= maxChoosableInteger; ++x) {
  13.             // 如果 x 已经被使用过了，则不能选择
  14.             if ((1 << x) & state) continue;
  15.             // 如果选择了 x 以后，大于等于了 desiredTotal，当前玩家赢
  16.             if (sum + x >= desiredTotal) {
  17.                 return true;
  18.             }
  19.             // 当前玩家选择了 x 以后，判断对方玩家一定输吗？
  20.             if (!dfs((1 << x) | state, sum + x, maxChoosableInteger, desiredTotal)) {
  21.                 return true;
  22.             }
  23.         }
  24.         return false;
  25.     }
  27. };

这个代码提交仍然会超时。

改进二：记忆化递归

所谓记忆化递归，就是保存已经知道的状态和结果，下一次遇到同样的参数就不用重新计算了。

为什么可以呢？

我们看到 464. 我能赢吗 - 图38函数中，有变化的参数只有两个 464. 我能赢吗 - 图39。也就是说，464. 我能赢吗 - 图40的输出，只与这两个变量有关。

同时，只要知道 464. 我能赢吗 - 图41，就能知道「已选择的数字」有哪些，因此也就确定了当前的 $sum$。

所以，只需要知道 464. 我能赢吗 - 图42，就能确定 464. 我能赢吗 - 图43的输出。

当递归执行的时候，会有重复计算问题，比如先选 $2$、再选 $1$的 464. 我能赢吗 - 图44与先选 464. 我能赢吗 - 图45再选 464. 我能赢吗 - 图46的 464. 我能赢吗 - 图47是相同的。

因此，我们可以缓存464. 我能赢吗 - 图48对应的递归结果，下次遇到同样的 464. 我能赢吗 - 图49就可以直接返回结果，不用再次计算了。

我们使用了一个 464. 我能赢吗 - 图50整数数组，存储所有可能的 464. 我能赢吗 - 图51的结果。

代码如下：

  1. class Solution {
  2. private:
  3.     // visited[i] == 0，说明没有计算过
  4.     // visited[i] == 1，说明计算过，结果为 true
  5.     // visited[i] == 2，说明计算过，结果为 false
  6.     int visited[1 << 21];
  7. public:
  8.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
  9.         // 判断当前做选择的玩家（先手），是否一定赢
  10.         // 开始时，state = 0，表示「公共整数集」中的所有数字都未被使用过
  11.         return dfs(0, 0, maxChoosableInteger, desiredTotal);
  12.     }
  14.     // 当前做选择的玩家是否一定赢
  15.     bool dfs(int state, int sum, int maxChoosableInteger, int desiredTotal) {
  16.         if (visited[state] == 1) return true;
  17.         if (visited[state] == 2) return false;
  18.         // 遍历可选择的公共整数
  19.         for (int x = 1; x <= maxChoosableInteger; ++x) {
  20.             // 如果 x 已经被使用过了，则不能选择
  21.             if ((1 << x) & state) continue;
  22.             // 如果选择了 x 以后，大于等于了 desiredTotal，当前玩家赢
  23.             if (sum + x >= desiredTotal) {
  24.                 visited[state] = 1;
  25.                 return true;
  26.             }
  27.             // 当前玩家选择了 x 以后，判断对方玩家一定输吗？
  28.             if (!dfs((1 << x) | state, sum + x, maxChoosableInteger, desiredTotal)) {
  29.                 visited[state] = 1;
  30.                 return true;
  31.             }
  32.         }
  33.         visited[state] = 2;
  34.         return false;
  35.     }
  37. };

改进三：提前判断

当把 $1$ 到 464. 我能赢吗 - 图52所有的数字全都累加，依然无法到达 $desiredTotal$， 先手一定输了。

为啥？因为我们问的是先手能不能赢，假如总和都达不到 $desiredTotal$，先手怎么赢？

另外一种情况是 464. 我能赢吗 - 图53，那么先手一定赢。

代码如下：

  1. class Solution {
  2. private:
  3.     // visited[i] == 0，说明没有计算过
  4.     // visited[i] == 1，说明计算过，结果为 true
  5.     // visited[i] == 2，说明计算过，结果为 false
  6.     int visited[1 << 21];
  7. public:
  8.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
  9.         if (maxChoosableInteger >= desiredTotal)
  10.             return true;
  11.         if (maxChoosableInteger * (maxChoosableInteger + 1) < desiredTotal)
  12.             return false;
  13.         // 判断当前做选择的玩家（先手），是否一定赢
  14.         // 开始时，state = 0，表示「公共整数集」中的所有数字都未被使用过
  15.         return dfs(0, 0, maxChoosableInteger, desiredTotal);
  16.     }
  18.     // 当前做选择的玩家是否一定赢
  19.     bool dfs(int state, int sum, int maxChoosableInteger, int desiredTotal) {
  20.         if (visited[state] == 1) return true;
  21.         if (visited[state] == 2) return false;
  22.         // 遍历可选择的公共整数
  23.         for (int x = 1; x <= maxChoosableInteger; ++x) {
  24.             // 如果 x 已经被使用过了，则不能选择
  25.             if ((1 << x) & state) continue;
  26.             // 如果选择了 x 以后，大于等于了 desiredTotal，当前玩家赢
  27.             if (sum + x >= desiredTotal) {
  28.                 visited[state] = 1;
  29.                 return true;
  30.             }
  31.             // 当前玩家选择了 x 以后，判断对方玩家一定输吗？
  32.             if (!dfs((1 << x) | state, sum + x, maxChoosableInteger, desiredTotal)) {
  33.                 visited[state] = 1;
  34.                 return true;
  35.             }
  36.         }
  37.         visited[state] = 2;
  38.         return false;
  39.     }
  41. };

复杂度

  • 时间复杂度：464. 我能赢吗 - 图54，464. 我能赢吗 - 图55是 464. 我能赢吗 - 图56。原因是每个数字都要判断，每次判断需要循环遍历 464. 我能赢吗 - 图57个数字。
  • 空间复杂度：464. 我能赢吗 - 图58。

总结

  1. 最开始的思路很简单，后续做了一些改进才能通过本题。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。