LeetCode 464. 我能赢吗（状态压缩+记忆化递归 / 博弈）

示例：
输入：
maxChoosableInteger = 10
desiredTotal = 11
输出：
false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

class Solution {
    unordered_map<int,bool> m;
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal)
            return false;//总和不够
        return win(maxChoosableInteger, desiredTotal, 0, 0);
    }
    bool win(int maxChoosableInteger, int desiredTotal, int point, int state) 
    {
        if(m.find(state) != m.end())
            return m[state];//重复的状态，直接读取
        for(int i = 1; i <= maxChoosableInteger; i++)
        {
            if(((state>>i)&1)==0)
            {	// 该二进制位为0 表示没有拿过该数
                if(point+i >= desiredTotal)
                    return true;
                int newstate = state | (1<<i);//新的状态，该位为1，用过了
                if(!win(maxChoosableInteger, desiredTotal, point+i, newstate))
                    return m[state] = true;
                    //上一个人在 newstate 下不能赢，那我在 state 状态下能赢
            }
        }
        return m[state] = false;
    }
};