DP recursive solution by using mask


  • 2
    A

    To solve problem strightforward dynamic programming approach was used. It has two states:

    1. What numbers are used - instead of using boolean array of size maxChoosableInteger there was used mask. Here it optimizes memory
    2. With what sum we use used numbers

    Our recursive DP will calculate if the user can win knowing only information about unusednumbers and the current sum. If for any possible move of the player his opponent will not lose then the player obviously will lose.

    Before calculating the answer we need to consider corner cases

    1. If desiredTotal = 0 then player always wins
    2. First player can't win if we can't get sum more than desiredTotal:
      formula for sum of elements between 1 and n: ((1+(n-1))/2) * n
    public class Solution {
        
        HashMap<Integer, Boolean> memory[];
        
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            memory = new HashMap[desiredTotal+1];   
            
            if (desiredTotal==0) return true;
            if (isMaxSumLessTotal(maxChoosableInteger,desiredTotal)) return false;
            
            return isWin(0, desiredTotal, maxChoosableInteger);
        }
        
        private boolean isMaxSumLessTotal(int maxChoosableInteger, int desiredTotal) {
            int maxPossibleSum = (1+maxChoosableInteger-1)*maxChoosableInteger/2;
            return (maxPossibleSum<desiredTotal);
        }
        
        private boolean isWin(int usedNumsMask, int total, int maxInteger) {
            if (total<=0) return false;
    
            if (isCalculated(usedNumsMask, total)) {
                return memory[total].get(usedNumsMask);
            }
            
            boolean canWin = false;
            for (int i=0; i<maxInteger; i++) {
                if ((usedNumsMask&(1<<i) )==0) {
                    int nmask = usedNumsMask|(1<<i);
                    canWin |= !isWin(nmask, total-(i+1), maxInteger);
                    if (canWin) break;
                }
            }
            
            updateMemory(usedNumsMask, total, maxInteger, canWin);
            return canWin;
        }
        
        private void updateMemory(int usedNumsMask, int total, int maxInteger, boolean canWin) {
            if (memory[total]==null) {
                memory[total] = new HashMap<>();
            }
            memory[total].put(usedNumsMask, canWin);
        }
        
        private boolean isCalculated(int usedNumsMask, int total) {
            return (memory[total]!=null && memory[total].containsKey(usedNumsMask));
        }
    }
    

  • 1
    P

    @amanchik What will be the time and space complexities to the problem? You didn't mention it.


  • 0
    A

    @pernekhan
    n = maxChoosableInteger
    m = desiredTotal

    time: O ( (n^2) * m)
    memory: O(n * m)


  • 0
    P

    @amanchik are you sure? I think it will be as below:

    N = maxChoosableInteger
    M = desiredTotal

    time: O( 2^N * M * N)
    memory: O(2^N * M)


Log in to reply
 

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