题目

cpp
class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0)
            return true;
        
        // 如果所有可选整数的和小于目标值，则无法稳赢
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal)
            return false;
        
        // 用于记录状态是否能够稳赢的哈希表
        unordered_map<int, bool> memo;
        
        // 初始状态为所有整数都未被使用
        int used = 0;
        
        return canWin(maxChoosableInteger, desiredTotal, used, memo);
    }
    
    bool canWin(int maxInt, int total, int used, unordered_map<int, bool>& memo) {
        if (memo.count(used))
            return memo[used];
        
        for (int i = 1; i <= maxInt; i++) {
            int mask = 1 << i;
            if ((used & mask) == 0) {  // 当前整数未被使用
                if (total <= i || !canWin(maxInt, total - i, used | mask, memo)) {
                    memo[used] = true;  // 当前状态能够稳赢
                    return true;
                }
            }
        }
        
        memo[used] = false;  // 当前状态无法稳赢
        return false;
    }

};