Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 464. Can I Win

---

題目：


解答：

class Solution {
private:
    unordered_map<int, bool> mp;

public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        auto dfs = [&](this auto&& dfs, int mask, int remain, int max_num) {
            if (mp.count(mask)) {
                return mp[mask];
            }

            for (int i = 1; i <= max_num; ++i) {
                int bit = 1 << i;

                if (!(mask & bit)) {
                    if (i >= remain) {
                        return mp[mask] = true;
                    }

                    if (!dfs(mask | bit, remain -i, max_num)) {
                        return mp[mask] = true;
                    }
                }
            }

            return mp[mask] = false;
        };

        if (desiredTotal <= 0) {
            return true;
        }

        int sum = (maxChoosableInteger * (maxChoosableInteger + 1) ) >> 1;
        if (sum < desiredTotal) {
            return false;
        }

        return dfs(0, desiredTotal, maxChoosableInteger);
    }
};