Quick C++ DP solution with bit maniplutaion (only 49ms)


  • 0
    S
    // reference to https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation/11
    // use bit manipulation and vector<int> as cache to speed up.
    class Solution {
        vector<int> cache;
        int state;
        int maxInt;
        public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
            if (sum < desiredTotal) return false;
            if (desiredTotal <= 0) return true;
            maxInt = maxChoosableInteger;
            state = 0;
            cache = vector<int> (1<<maxChoosableInteger, -1);
            return helper(desiredTotal);
        }
    
        bool helper(int desiredTotal) {
            if (desiredTotal <= 0) return false;
            if (cache[state] != -1) return cache[state];
            int mask = 1;
            for (int i=0; i<maxInt; ++i) {
                if (!(state & mask)) {
                    state |= mask;
                    if (!helper(desiredTotal-i-1)) {
                        state &= ~mask;
                        cache[state] = 1;
                        return true;
                    }
                    state &= ~mask;
                }
                mask <<= 1;
            }
            cache[state] = 0;
            return false;
        }
    
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.