一、题目

在 "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

二、代码

class Solution {
     public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        // 题目规定，desiredTotal == 0则先手赢
        if (desiredTotal == 0) {
            return true;
        }
        // 如果可选择的数字总加和都小于desiredTotal，每个数只能选一次，那么无论怎么选，desiredTotal都不可能小于0，题目规定这种情况先手输
        if ((1 + maxChoosableInteger) * maxChoosableInteger >> 1 < desiredTotal) {
            return false;
        }

        // 创建dp表，记录所有可能的数组存在情况，每一个数有存在或者不存在两种状态，一共有maxChoosableInteger个数，所以一共有2^maxChoosableInteger种状态，这就是需要开辟dp数组的大小
        int[] dp = new int[1 << (maxChoosableInteger)];
        // (1 << maxChoosableInteger) - 1：将代表每一个数状态的二进制位都设置为1，表示初始存在状态
        return process((1 << maxChoosableInteger) - 1, desiredTotal, maxChoosableInteger, dp);
    }
    // status：利用整形的二进制位来表示每一个数的存在状态，1表示存在，0表示已经被拿取
    // rest：在每一轮取数过程中，desiredTotal还剩下多少
    // n：常数参，表示一共有多少个数供玩家选择
    // dp[status]：记录每一种状态下，先手玩家的胜负。0表示还没有记录过该状态先手玩家的胜负，1表示该状态先手胜利，-1表示该状态先手失败
    // 返回值：在先手和后手都绝顶聪明的情况下，先手会不会赢。如果先手会赢返回true，否则返回false。
    public boolean process(int status, int rest, int n, int[] dp) {
        // 如果dp中已经记录了该状态的结果，直接返回
        if (dp[status] != 0) {
            return dp[status] == 1 ? true : false;
        }
        
        // 当rest > 0时
        if (rest > 0) {
            // 遍历每一个数，找还没有被人拿走的数来进行尝试，将所有可能的选择都尝试一遍
            for (int i = 0; i < n; i++) {
                // (status & (1 << i)) == (1 << i)：说明要拿的数对应的二进制位是1，表示还没有被人拿走，可以尝试将其拿走
                if ((status & (1 << i)) == (1 << i)) {
                    // 将i+1这个数拿走以后，去执行后续的递归，如果后续的递归返回false，表示下层的递归的先手输了，而下层递归的先手就是本层递归的后手，本层递归后手输了，那么就表示本层递归先手赢了。则返回ture
                    // status & (~(1 << i)：将i+1这个数对应的二进制位设置为0，表示已经被拿走   
                    // rest - (i + 1)：将rest减掉选择的(i + 1)这个数
                    if (!process(status & (~(1 << i)), rest - (i + 1), n, dp)) {
                        // 将结果记录在dp中
                        dp[status] = 1;
                        return true;
                    }
                }
            }
        }
       
        // 执行到这里有两种情况：
        // 1、rest < 0，那么回直接跳过上面的for循环直接到这里，当rest小于0，那么先手肯定就是输了
        // 2、上面执行完循环，先手尝试了所有可能的拿法，都没找到能让自己胜利的拿法，则说明先手不管怎么拿都会输
        // 将结果记录在dp中
        dp[status] = -1;
        return false;
    }
}