LeetCode 464. 我能赢吗

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    unordered_map<int,bool> res;
    bool Attemp(int n,const int len,int currentTotal,const int desiredTotal){
        if(res.count(n)){return res[n];}
        for(int i=len;i>=1;i--){
            if(n>>i-1&1){
                if(i+currentTotal>=desiredTotal){return res[n]=true;}
                if(!Attemp(n^(1<<i-1),len,i+currentTotal,desiredTotal)){return res[n]=true;}
            }
        }
        return res[n]=false;
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if((1+maxChoosableInteger)/2*maxChoosableInteger<desiredTotal) return false;
        int n=(1<<maxChoosableInteger)-1;
        return Attemp(n,maxChoosableInteger,0,desiredTotal);
    }
};

参考

  1. https://leetcode.cn/problems/can-i-win/ ↩