leetcode464 Can I Win

思路：
博弈。
实现：
 1 class Solution 
 2 {
 3 public:
 4     bool dfs(int cur, int len, int sum, int des, vector<int>& dp)
 5     {
 6         if (sum >= des) return false;
 7         if (dp[cur] != -1) return dp[cur];
 8         for (int i = 0; i < len; i++)
 9         {
10             int tmp = 1 << i;
11             if (!(cur & tmp))
12             {
13                 if (!dfs(cur | tmp, len, sum + i + 1, des, dp)) 
14                     return dp[cur] = true;
15             }
16         }
17         return dp[cur] = false;
18     }
19     bool canIWin(int maxChoosableInteger, int desiredTotal) 
20     {
21         if (!desiredTotal) return true;
22         if ((maxChoosableInteger * (maxChoosableInteger + 1) / 2) < desiredTotal)
23             return false;
24         vector<int> dp(1100000, -1);
25         return dfs(0, maxChoosableInteger, 0, desiredTotal, dp);
26     }
27 };