image.png

1.题解

用map记录所有状态的属性，并且依次for循环枚举每一个元素，如果没有访问过就尝试去访问，如果访问过就忽视它继续continue。

  1. class Solution {
  2. public:
  3.     bool dfs(int stat,unordered_map<int,int> &dp,int desiredTotal,int maxChoosableInteger){
  4.         if(dp.count(stat)) return dp[stat];
  5.         for(int i=1; i <= maxChoosableInteger ;i++){
  6.             int x = (1<<(i-1));
  7.             if((stat & x)!=0) continue;
  9.             if(i>=desiredTotal || !dfs(stat|x,dp,desiredTotal-i,maxChoosableInteger)) return dp[stat] = true;
  10.         }
  11.         return dp[stat] = false;
  12.     }
  13.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
  14.         if(maxChoosableInteger>=desiredTotal)return true;
  15.         if(maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal){
  16.             return false;
  17.         }
  18.         unordered_map<int,int> dp;
  19.         return dfs(0,dp,desiredTotal,maxChoosableInteger);
  20.     }
  21. };