LeetCode 464 我能赢吗

LeetCode 464 我能赢吗

题目链接

我学习的第一道状态压缩dp的题，很有趣，难点在于不能重复使用数字。目前leetcode上题解还比较少，但是我个人感觉这道题似乎很常见。方法是dp，而且特殊的是这道题使用自顶向下的动态规划更优，因为不是所有的情况都有必要求出来。

学习这道题，我主要参考了这篇链接。这是我第一次看英文版leetcode，英语题解没有想象中难理解，单词都认识，句子也可以看懂，万一有不懂的可以结合机器翻译辅助理解。如果链接跳到了中文版，你就把地址手动去掉-cn吧。另外我也写了详细注释，希望可以帮到大家。

保存状态，由于题设说最大值不会大于20，因此可以采用位运算的方式。int有32位，可以满足需求。用int类型的maked来表示已选择的数组，比如二进制数：00000000 00000000 00000000 00001001（即int值的9）可以表示数字1和4已经被选择。

既然要用位运算，就需要了解其中的一些含义，
1.marked & (1 << i)表示marked的二进制表示形式在第(i+1)位是否是1，对于这道题即第(i+1)位是否已经被挑选了
2.marked ^ (1 << i)表示marked的二进制表示形式的第(i+1)位设置为1，对于这道题即把第(i+1)位选上。（与marked | (1 << i)效果相同）

//状态压缩dp
class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        //如果预期值小于等于可选择的最大的数，选任何数都可以赢
        if (desiredTotal <= maxChoosableInteger) {
            return true;
        }
        //如果预期值大于可选数的和，无论如何，先出手的玩家都不能赢（和不能大于等于预期值）
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) {
            return false;
        }

        //dp[i]表示的是 先选择的情况下 已选择的是i时 的输赢情况，若i=0，表示都没有选，即给定条件下先出手输赢的情况，即最后的答案
        //长度取1 << maxChoosableInteger，原因是dp最极端的情况是，假设有n个数，n个数都需要取，有111...111(2进制)，它的大小是2^n-1，从0开始算到这个数，一共有2^n个数，即1 << n
        int[] dp = new int[1 << maxChoosableInteger];

        return dfs(maxChoosableInteger, desiredTotal, dp, 0);
    }

    private boolean dfs(int maxChoosableInteger, int desiredTotal, int[] dp, int marked) {
        //如果还剩下的值为负，说明前一手选择已经赢了，因此它输了，返回false
        if (desiredTotal <= 0) {
            return false;
        }
        //首先判断这种选择之前是否曾经判断过，如果判断过，就直接返回答案，不需要再判断一次。通过dp已经对这种情况记忆化了
        if (dp[marked] != 0) {
            return dp[marked] == 1;
        }
        //这是一种新情况，开始判断
        boolean win = false;
        for (int i = 0; i < maxChoosableInteger; i++) {
            //判断i是否被选择过，没有被选择过的数字才可以选择
            if ((marked & (1 << i)) == 0) {
                win = win || !dfs(maxChoosableInteger, desiredTotal - (i + 1), dp, marked ^ (1 << i));
            }
        }

        dp[marked] = win ? 1 : -1;

        return win;
    }
}