C++ easy to understand DFS solution with explanation


  • 3
    I

    Player1 can win if and only if they can make a move after which player2 will lose no matter how they move. So we can check all possible moves of player1 and call the same function to see if player2 will lose after this move. This is the main idea. I use caching to memorize states for each possible desiredTotal and set of chosable integers. Since maxChoosableInteger is not greater than 20, all currently possible moves can be represented as a bit flag.

    class Solution {
    public:
        bool canWin(int key, int desiredTotal,vector<unordered_map<int,bool>> &cache, int mx) {
            if(cache[desiredTotal-1].find(key) != cache[desiredTotal-1].end())
               return cache[desiredTotal-1][key];
            for(int i = mx-1; i >= 0;--i)
               if(key & (1 << i))
               {
                   key ^= (1 << i);
                   if(i+1 >= desiredTotal || !canWin(key,desiredTotal-i-1,cache,mx))
                   {
                      cache[desiredTotal-1][key] = true;
                      key |= (1 << i);
                      return true;
                   }
                   key |= (1 << i);
               }
            cache[desiredTotal-1][key] = false;
            return false;
        }
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(desiredTotal <= 1)
              return true;
            if(maxChoosableInteger*(maxChoosableInteger+1) < desiredTotal*2)
               return false;
            vector<unordered_map<int,bool>> cache(desiredTotal);
            vector<bool> v(maxChoosableInteger,true);
            int key = (1 << maxChoosableInteger)-1; 
            return canWin(key,desiredTotal,cache,maxChoosableInteger);
        }
    };
    

  • 1
    S

    if(maxChoosableInteger*(maxChoosableInteger+1) < desiredTotal*2)
    return false;
    Why?


  • 0
    I

    It means that the sum of numbers from 1 to maxChoosableInteger, which is (1+maxChoosableInteger)*maxChoosableInteger/2 is less than desiredTotal and desiredTotal will never be reached.


  • 0
    S

    @i9r0k I have a question about the update of the key. Could you help me solve the problem?

    Question:
    for(int i = mx-1; i >= 0;--i)
    if(key & (1 << i))
    {
    key ^= (1 << i);
    if(i+1 >= desiredTotal || !canWin(key,desiredTotal-i-1,cache,mx))
    {
    cache[desiredTotal-1][key] = true;
    key |= (1 << i); //Is this necessary? why?
    return true;
    }
    key |= (1 << i);
    }


Log in to reply
 

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