464.我能赢吗

链接：464.我能赢吗
难度：Medium
标签：位运算、记忆化搜索、数学、动态规划、状态压缩、博弈
简介：判断先出手的玩家是否能稳赢。

题解 1 - javascript

• 编辑时间：2021-07-29
• 执行用时：1008ms
• 内存消耗：161.2MB
• 编程语言：javascript
• 解法介绍：记忆化 dfs。

var canIWin = function (maxChoosableInteger, desiredTotal) {
  if (((maxChoosableInteger + 1) * maxChoosableInteger) / 2 < desiredTotal) return false;
  const map = {};
  return dfs();
  function dfs(num = 0, total = desiredTotal) {
    if (map[num]) return map[num];
    if (total <= 0) return (map[num] = true);
    for (let i = 1; i <= maxChoosableInteger; i++) {
      if (num & (1 << i)) continue;
      if (i >= total || !dfs(num | (1 << i), total - i)) return (map[num] = true);
    }
    return (map[num] = false);
  }
};

题解 2 - cpp

• 编辑时间：2022-05-22
• 执行用时：856ms
• 内存消耗：85.7MB
• 编程语言：cpp
• 解法介绍：dfs,记忆化，当前人赢的时候说明下一层级需要输。

class Solution {
   public:
    int maxChoosableInteger, desiredTotal, maxBit;
    unordered_map<int, bool> m;
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)
            return false;
        this->maxBit = 1 << maxChoosableInteger;
        this->maxChoosableInteger = maxChoosableInteger;
        this->desiredTotal = desiredTotal;
        return dfs(0, 0);
    }
    bool dfs(int used, int sum) {
        if (m.count(used)) return m[used];
        if (sum >= desiredTotal) return m[used] = true;
        if (check(used, sum)) return m[used] = true;
        int ans = false;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            int bit = 1 << i;
            if (used & bit) continue;
            ans = ans || !dfs(used | bit, sum + i);
        }
        return m[used] = ans;
    }
    bool check(int used, int sum) {
        int num = desiredTotal - sum;
        if (num > maxChoosableInteger) return false;
        for (int i = num; i <= maxChoosableInteger; i++) {
            int bit = 1 << i;
            if (!(used & bit)) return true;
        }
        return false;
    }
};