dp solution in c++ with comments


  • 1
    S

    I think the key to this problem is to use some bitwise operation to record what numbers have been used during the game to minimize the size of hash table as much as possible.

     class Solution {
     public:
     	bool canIWin(int maxChoosableInteger, int desiredTotal) {
     		if(desiredTotal == 0) return true;
     
     		if((maxChoosableInteger+1) * maxChoosableInteger / 2 < desiredTotal)
     			return false;
     
     		unordered_map<int, bool> dp;
     
     		// a bit in record being equal to 1 means a number is available
     		// for example if record is ..1000, it means number 3 has not been used,
     		// for convenience we do not use the least significant digit.
     		int record = 0;
     		for(int i = 0; i < maxChoosableInteger+1; i++) {
     			record = (record << 1) + 1;
     		}
     		return f(desiredTotal, record, dp);
     	}
     
     	bool f(int dt, int record, unordered_map<int, bool> &dp)
     	{
     		if(dp.count(record)) {
     			return dp[record];
     		}
     		
     		// we know maxChoosableInteger wont be larger than 20
     		for(int i = 20; i > 0; i--) {
     			int bit = 1 << i;
     
     			// if this number has not been used
     			if(record & bit) {
     				if(i >= dt) {
     					dp[i] = true;
     					return true;
     				}
     				// mark number i so it has been used and check whether the opponent
     				// can win. Notice that due to the annoyance of [] operator
     				// automatically inserting value into a set in c++, we should not
     				// use dp[...] = f(..., dp) to avoid changing dp BEFORE the
     				// function is called.
     				bool t = f(dt-i, record^bit, dp);
     				dp[record^bit] = t;
     				if(t == false) {
     					return true;
     				}
     			}
     		}
     		return false;
     
     	}
     
     };

  • 0

    what a great solution!!!!
    Brilliant thought.

    and

    if(i >= dt) {
     	    //dp[i] = true;      
                return true;
     }
    

    I think this line is useless.


  • 2
    E

    And since 2^21/4B/1024/1024=8MB, I replace hashmap(636 ms) with vector/array(75 ms);
    I'm a beginner and looking forward for your advice.

    class Solution {
    private:
    	vector<int> *winSet;
    	bool canIWinAux(int numSet, int total) {
    		int maxnum = maxNum(numSet);
    		if (maxnum >= total) return true;
    		if (winSet->at(numSet) != -1) return winSet->at(numSet);
    		for (int num = 1; num <= maxnum; num++) {
    			int mask = 1 << (num-1);
    			//	skip used number
    			if (!(numSet&mask)) continue;
    			//	skip if take num as first choice
    			if (canIWinAux((int)(numSet&(~mask)), total - num)) continue;
    			//	otherwise this num is the smart choice
    			winSet->at(numSet) = true;
    			return true;
    		}
    		//	have tried every number in numSet and fail to win
    		winSet->at(numSet) = false;
    		return false;
    	}
    
    	//	return the maximum number avaliable in the numSet
    	int maxNum(int numSet) {
    		int firstBit = 0;
    		while (numSet) {
    			firstBit++;
    			numSet >>= 1;
    		}
    		return firstBit;
    	}
    
    
    public:
    	bool canIWin(int maxChoosableInteger, int desiredTotal) {
    		if (desiredTotal>maxChoosableInteger*(maxChoosableInteger + 1) / 2) return false;
    		if (desiredTotal <= maxChoosableInteger) return true;
    		if (desiredTotal % (1 + maxChoosableInteger) == 0 && maxChoosableInteger % 2 == 0) return false;
    
    		//	numSet: the k-nd bit stands for number k; 1 is usable, 0 is used, -1 is unknown.
    		int numSet = (1 << (maxChoosableInteger))-1;
    		winSet = new vector<int>(1 << maxChoosableInteger, -1);
    		return canIWinAux(numSet, desiredTotal);
    	}
    };
    

Log in to reply
 

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