C++ DP solution 15ms 20 lines


  • 6

    alt text

    class Solution {
    public:
      bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        int sum = ((maxChoosableInteger + 1) * maxChoosableInteger) >> 1;
        if (sum < desiredTotal) return false;
        mp = vector<int>(1 << maxChoosableInteger, -1);
        return canWin(0, maxChoosableInteger, desiredTotal);
      }
    private:
      vector<int> mp;
      bool canWin(int used, const int &maxChoosableInteger, int desiredTotal) {
        if (mp[used] != -1) return mp[used];
        for (int i = maxChoosableInteger, bits = 1 << (maxChoosableInteger - 1); i >= 1; --i, bits >>= 1) {
          if ((used & bits) != 0) continue;
          if (i >= desiredTotal || !canWin(used | bits, maxChoosableInteger, desiredTotal - i)) {
            mp[used] = 1;
            return true;
          }
        }
        mp[used] = 0;
        return false;
      }
    };
    

  • 1
    P

    It's amazing how concise and neat your solution combining with bit operations!


  • 0

    a little don't unstand.
    sad


  • 0
    S

    Can you explain it?


  • 2
    B

    @sangshuhao7 said in C++ DP solution 15ms 20 lines:

    Can you explain it?

    we have to try out all combinations to figure out the solution. However, we can store the result to avoid duplicate run. For example, the choose sequence of 1234 is the same as 3412. In algorithm, it is called memoization.

    back to this specific solution, he used a large array to record the result. And most importantly, he used binary bits to represent the used number so 1234 and 3412 would be the same. The binary bits would be the index of the large array.

    below I made slight change so the algorithm is more clear. We use binary bits to record the used number, and use HashSet to store the result. Once we find a guaranteed win or loose, we record the result in HashSet.

    class Solution {
    public:
        unordered_set<int>win, lose;
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(maxChoosableInteger >= desiredTotal) return true;
            if( (maxChoosableInteger*(maxChoosableInteger+1) >> 1) < desiredTotal) return false;
            return canIWin(0, maxChoosableInteger, desiredTotal);
        }
        
        bool canIWin( int usedBits, int maxChoosableInteger, int desiredTotal)
        {
            if(desiredTotal <= 0) return false;
            if(win.find(usedBits) != win.end()) return true;
            if(lose.find(usedBits) != lose.end()) return false;
            for(int i = maxChoosableInteger; i > 0; i-- )
            {
                int bit = 1 << i;
                if(usedBits & bit) continue;
                if(!canIWin(usedBits | bit, maxChoosableInteger, desiredTotal - i))
                {
                    win.insert(usedBits);
                    return true;
                }
            }
            lose.insert(usedBits);
            return false;
        }
    };

  • 0
    T

Log in to reply
 

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