1. state = state | (1 << i)
    2. (state & (1 << i)) != 0 // 表示位标记
    3. // 464. 我能赢吗？ https://leetcode-cn.com/problems/can-i-win/
    4. // 记忆化dfs、博弈
    5. class Solution {
    6. public:
    7.     map<pair<int, int>, bool> mp; // <state, sum>, ret
    8.     bool canIWin(int maxChoosableInteger, int desiredTotal) {
    10.         if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
    11.             return false;
    12.         }
    13.         for (int i = 1; i <= maxChoosableInteger; i++) {
    14.             if (dfs(maxChoosableInteger, desiredTotal, 1 << i, i)) {
    15.                 return true;
    16.             }
    17.         }
    18.         return false;
    19.     }
    21.     bool dfs(int maxChoosableInteger, int desiredTotal, int state, int sum)
    22.     {
    23.         if (sum >= desiredTotal) {
    24.             return true;
    25.         }
    26.         if (mp.count({state, sum})) {
    27.             return mp[{state, sum}];
    28.         }
    29.         bool ret = true;
    30.         for (int i = 1; i <= maxChoosableInteger; i++) {
    31.             if ((state & (1 << i)) != 0) {
    32.                 continue;
    33.             }
    34.             if (dfs(maxChoosableInteger, desiredTotal, (state | (1 << i)), sum + i) == true) {
    35.                 ret = false;  // 后手赢了，表示当前手输了，返回false
    36.                 break;
    37.             }
    38.         }
    39.         mp[{state, sum}] = ret; 
    40.         return ret;
    41.     }
    42. };