464. 我能赢吗

464. 我能赢吗

dfs+记忆化+状态压缩

class Solution {
public:

    bool dfs(int state,int maxnum,int tar,vector<int>&memo){
        if(memo[state]<2)return memo[state];

        for(int i=1;i<=maxnum;i++){
            if (state & (1 << (i - 1)))
                continue;
            int tmp=1<<(i-1);
            if(i>=tar || !dfs(state|tmp,maxnum,tar-i,memo)){
                memo[state]=1;
                return true;
            }
        }

        memo[state] = 0;
        return false;
    }
    bool canIWin(int maxnum, int tar) {
        if (maxnum > tar)return true;
        // 所有数都用完还达不到tar的时候，就是两边都输
        // 而dfs返回的是对方输的时候，判自己赢
        // 这种情况下就不是非输即赢，因此需要特判
        if ((maxnum + 1) * maxnum / 2 < tar)return false;

        vector<int>memo(1<<maxnum,2);

        return dfs(0,maxnum,tar,memo);
    }
};