464. 我能赢吗（精髓）

  • 千万注意这题是累计整数和

    1. class Solution {
    2. public:
    3.   unordered_map<int, bool> memo;//记忆化剪枝
    5.   bool canIWin(int maxChoosableInteger, int desiredTotal) {
    6.       if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
    7.           return false;
    8.       }//特殊情况。
    9.       return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    10.   }
    12.   bool dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {//用一个整数来表示已经选择的数字集合，看二进制位i是否取1来判断是否选择了i。
    13.   // 每一层的玩家不同, 但是目的都是当前层能获胜 || 下一层不能获胜则当前层能获胜
    14.       if (!memo.count(usedNumbers)) {//如果记忆中没有
    15.           bool res = false;
    16.           for (int i = 0; i < maxChoosableInteger; i++) {
    17.               if (((usedNumbers >> i) & 1) == 0) {//当前位置没有选择
    18.                   if (i + 1 + currentTotal >= desiredTotal) {//选当前位后可以达成目标。
    19.                       res = true;
    20.                       break;
    21.                   }
    22.                   if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {//这里表示对方输了。因为对方最终无法达到目标
    23.                       res = true;
    24.                       break;
    25.                   }
    26.               }
    27.           }
    28.           memo[usedNumbers] = res;//使用记忆化，不用浪费时间。
    29.       }
    30.       return memo[usedNumbers];
    31.   }
    32. };

    猫和老鼠系列