House Robber

Today, we are going to study Leetcode’s house robber. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police (you cannot rob two adjacent homes). Let’s list out some facts.

Fact 1: Working from the end of the list to index 0, at each house, you are given the choice to rob a house or not. If you choose to rob a house and get its value, you cannot rob the n-1 house.

Fact 2: You can maximize the value obtain from the first n houses by maximizing the value obtained from the first n-1 houses (and not including the value of the n^th house) or maximizing the value of the first n-2 house plus the value of the n^th house.

This sure sounds like a dynamic programing problem.

Overlapping Sub-problem – Yes. We can see that as we break the problem down, we are repeating the subproblems multiple times.

Optimal Substructure – Yes. Fact 2 describes why finding the optimal solution to the subproblems (n-1, n-2….) leads to the optimal solution of finding the maximum value obtainable considering all n homes.

Base case(s) – the two base cases for this solution is f(0) = value[0].

DP Table

In this problem, our cache table will simply store at index n, the maximum obtainable value of the first n homes.

Memoization

class Solution {
    private int[] cache;
    public int rob(int[] nums) {
        if (nums.length == 0){
            return 0;
        }                        
        cache = new int[nums.length];  
        
        // house values can be 0
        Arrays.fill(cache, -1);
        
        return robHouse(nums, nums.length-1);        
    }
    
    public int robHouse(int[] nums, int n) {      
        // base case n == 0
        if (n == 0) {            
            return nums[0];
        } else if (cache[n] > -1) {
            return cache[n];
        }
        
        int includeNth = n-2 >= 0 ? robHouse(nums, n-2) + nums[n] : nums[n];
        int notIncludeNth = robHouse(nums, n-1);
        
        
        int maxValue = includeNth > notIncludeNth ? includeNth: notIncludeNth;
        cache[n] = maxValue;   
        return maxValue;
    }
}

Tabulation

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0){
            return 0;
        }                   
        int[] cache = new int[nums.length];    
        cache[0] = nums[0];
        
        for(int i=1; i= 0 ? cache[i-2] + nums[i] : nums[i];
            int notIncludeNth = cache[i-1];                
            cache[i] = includeNth > notIncludeNth ? includeNth: notIncludeNth;
        }        
        return cache[nums.length-1];      
    }
}

Conclusion

This is a relatively simple question, but the wording often throws some people off. One of the difficulties candidates encounter (including myself the first time I saw this problem) was understanding what “two adjacent homes” means. Given 3 homes in the order of [A, B, C]:

1. It means that you cannot rob two sequential home in a row. I.e. [A, B] or [B, C]
2. A common misconception is that you cannot rob homes A and C because B will have ‘two adjacent homes’ that have been robbed.

This makes the problem much more difficult so if you are issuing this question, it’s important confirm that the candidate understands the reequipments clearly.