464. Can I Win

Link

Solution

TopDown + meno

Key is to transfer the choosable num status into an Integer

I use a boolean array to denote which numbers have been chosen, and then a question comes to mind, if we want to use a Hashmap to remember the outcome of sub-problems, can we just use Map<boolean[], Boolean> ? Obviously we cannot, because the if we use boolean[] as a key, the reference to boolean[] won't reveal the actual content in boolean[].

Since in the problem statement, it says maxChoosableInteger will not be larger than 20, which means the length of our boolean[] array will be less than 20. Then we can use an Integer to represent this boolean[] array. How?

Say the boolean[] is {false, false, true, true, false}, then we can transfer it to an Integer with binary representation as 00110. Since Integer is a perfect choice to be the key of HashMap, then we now can "memorize" the sub-problems using Map<Integer, Boolean>.

  HashMap<Integer, Boolean> result;
    boolean[] numPickStatus;
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        result = new HashMap<>();
        numPickStatus = new boolean[maxChoosableInteger+1];
        int sum = (maxChoosableInteger + 1) * maxChoosableInteger /2;
        if(sum < desiredTotal) return false;
        if(0 >= desiredTotal) return true;
        return helper(desiredTotal);
    }
    
    public boolean helper(int desiredTotal){
        if(desiredTotal <= 0) return false;
        
        int key = getValue();
        if(result.containsKey(key)){
            return result.get(key);
        }
        for(int i = 1; i < numPickStatus.length; i++){
            if(!numPickStatus[i]){
                numPickStatus[i] = true;
                if(!helper(desiredTotal-i)){
                    result.put(key, true);
                    numPickStatus[i] = false;
                    return true;
                }
                numPickStatus[i] = false;
            }
        }
        result.put(key, false);
        return false;
    }
    
    public int getValue(){
        int ret = 0;
        for(int i = 1; i < numPickStatus.length; i++){
            if(numPickStatus[i]){
                ret |= (1 << i);
            }
        }
        return ret;
    }