博客

题目描述：

解法一（递归搜索）（超时）：

class Solution {
public:
    bool canWin(const int& maxChoosableInteger, int desired, unordered_map<int, bool> record) {
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (record.count(i) != 0 && record[i] == 1) continue;            //数字被使用过了
            else{
                record[i] = 1;
                if (i >= desired || !canWin(maxChoosableInteger, desired - i, record)) { //递归
                    return true;
                }
                record[i] = 0;
            }
        }
        return false;
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((maxChoosableInteger + 1)*maxChoosableInteger / 2<desiredTotal) return false; //特殊情况
        unordered_map<int, bool> record;                            //使用map来记录数字有没有被使用过
        return canWin(maxChoosableInteger, desiredTotal, record);
    }
};

解法二（带备忘录的递归搜索）：

上面一种解法显然会有大量的重复计算！ 时间复杂度O(n!)

class Solution {
public:
    bool canWin(const int& maxChoosableInteger, int desired, int used, unordered_map<int, bool>& record) {
        if (record.count(used))                                     //used标识数字是否被用过
            return record[used];
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (!((1 << i)&used)) {
                if (i >= desired || !canWin(maxChoosableInteger, desired - i, used | (1 << i), record)) {
                    record[used] = 1;
                    return true;
                }
            }
        }
        record[used] = 0;
        return false;
    }
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((maxChoosableInteger + 1)*maxChoosableInteger / 2<desiredTotal) return false;
        unordered_map<int, bool> record;                            //备忘录
        return canWin(maxChoosableInteger, desiredTotal, 0, record);
    }
};