464. 我能赢吗

题目

在 “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 <= 20
0 <= desiredTotal <= 300

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/can-i-win
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

没有自己做出来，看了官解思路才明白，博弈的题目就不太好想，关键是要想清楚自己如何赢，核心思想如下（引用自官解）：

概括起来就是两点：

• 如果自己可以选择一个数，使总和不小于desiredTotal，那么就可以获胜。
• 如果自己选择一个数后，对手怎么都是输的话，那自己就可以获胜。
• 如果上两点无法满足，那么会输。

理解了上述思路，代码实现上就简单了。使用一个变量used，其二进制表示maxChoosableInteger个数的使用情况，二进制位为0表示没有被使用，为1表示使用了。另外，需要记忆化，不然会超时。

代码

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // 坑死了，这里必须判断，所有数之和都不够desiredTotal，那肯定无法赢
        // 不加会返回true，因为判断了对手会输，就认为自己赢了，其实谁都赢不了
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) {
            return false;
        }
        return dfs(maxChoosableInteger, 0, 0, desiredTotal, new int[1 << maxChoosableInteger]);
    }
    private boolean dfs(int maxChoosableInteger, int used, int sum, int desiredTotal, int[] mem) {
        if (mem[used] > 0) {
            return mem[used] == 1;
        }
        for (int i = 1; i <= maxChoosableInteger; i++) {
            // 数字i没有使用
            if ((used >> (i - 1) & 1) == 0) {
                // 如果自己可以选择一个数，使总和不小于desiredTotal，那么就可以获胜
                if (sum + i >= desiredTotal) {
                    mem[used] = 1;
                    return true;
                }
                // 如果自己选择一个数后，对手怎么都是输的话，那自己就可以获胜
                if (!dfs(maxChoosableInteger, used | 1 << (i - 1), sum + i, desiredTotal, mem)) {
                    mem[used] = 1;
                    return true;
                }
            }
        }
        // 自己输了
        mem[used] = 2;
        return false;
    }
}