题目描述

题目大意：两个人玩游戏，从1～maxChoosableInteger中任选一个数字，第一个人先选，第二个人后选，每个人选过的数字就不能再选了～两个人谁先加起来总和超过desiredTotal谁就赢，问给出数字，第一个人能否赢得比赛

样例

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出:
false

算法

(dfs) $O(2^m)$

由于给定的正整数小于max,因此我们可以用status表示当前的状态，最低位表示1是否被选取，0表示没有被选取，1表示被选取。
dfs的过程中，我们每次从可以选择的数中选择一个数，如果当前选择的数能够大于desire，那么就赢了。 如果我们当前选择了这个数，并且对手在剩下的状态中输了，那么我们也赢了。

如果赢了或者输了，利用dp数组记录一下状态，因为这个状态有可能多次重复出现，我们只需要算一次就够了。

时间复杂度：由于我们采用的是dfs ,对于1到maxChoosableInteger中间的数都可能取或者不取，那么复杂度为$O(2^m)$

C++ 代码

class Solution {
public:
    bool canIWin(int max, int desire) {
        int status = 0;

        if (desire<=1) return true;
        if (max*(max+1) < desire*2) return false;



        vector<unordered_map<int,bool>>dp(desire+1);

        return Caniwin(status,dp,max,desire);

    }
    bool Caniwin(int status,vector<unordered_map<int,bool>>&dp,int maxn,int desire){
        if (dp[desire].count(status))
            return dp[desire][status];
        for (int i=maxn-1;i>=0;--i){
            if (!(status&(1<<i))){
                status |= (1<<i);
                if (i+1>=desire || !Caniwin(status,dp,maxn,desire-i-1)){
                    dp[desire][status] = true;
                    return true;
                }
                status ^= (1<<i);

            }

        }
        dp[desire][status] = false;
        return false;

    }


};