Java Memoized DP Solution


  • 3
    public int findIntegers(int num) {
      return findIntegers(num, new HashMap<>());
    }    
    
    public int findIntegers(int num, Map<Integer, Integer> memo) {
        if (num <= 2) return num + 1; // base case
        if (memo.containsKey(num)) return memo.get(num); // check if this result has already been computed   
        
        int msb = 31 - Integer.numberOfLeadingZeros(num); // retrieve index of most significant bit
        int subNum = (1 << msb) - 1, subNum2 = ~(1 << msb) & num;
        if (subNum2 >= 1 << msb - 1) subNum2 = subNum >> 1;
        int result = findIntegers(subNum, memo) + findIntegers(subNum2, memo);
        
        memo.put(num, result); // add result to memo
        return result;
    }
    

  • 0
    T

    can you give us some explanation here? What do these three lines do?

        int subNum = (1 << msb) - 1, subNum2 = ~(1 << msb) & num;
        if (subNum2 >= 1 << msb - 1) subNum2 = subNum >> 1;
        int result = findIntegers(subNum, memo) + findIntegers(subNum2, memo);
    

  • 0
    Y

    @tiandiao123 My equivalent approach which is a little more self-explanatory

        int res = 0;
        int x = Integer.highestOneBit(num); // e.g. highestOneBit(1011) = 1000
        res += findIntegers(x - 1); // e.g. x = 1000, x - 1 = 0111. 
        int y = Integer.highestOneBit(num - x); 
        if (y << 1 == x) res += findIntegers(y - 1);
        else res += findIntegers(num - x);
        m.put(num, res);
        return res;
    

    A few examples:
    f(110010) = f(011111) + f(001111)
    f(101010) = f(011111) + f(001010)


Log in to reply
 

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