House Robber

House Robber I (LC.198)

You plan to rob a neighborhood. The constraint is that you are not allowed to rob adjacent houses. And your objectively is obviously to maximize your earning. Given an array where money[i] = money stored at house_i, return the maximum amount of money you can rob.

Example

Input: [3, 8, 1, 2, 5, 6]
Return: 8 + 2 + 6 = 16

Analysis

Maximization/minimization on an array usually can be solved with DP. So does this one.

Approach

1. define optimal subproblems by prefix
    rob(n) = max amount of money at house n
2. solve by prefix, 2 optionas, rob nth house or skip it
    rob(n) = Math.max(rob(n-1), rob(n-2) + money[n]);
3. topo order
    for i from 2 to n
4. init base cases
    rob(0) = 0
    rob(1) = money[0]
5. answer
    return rob(n)

Code

public int rob(int[] money) {
    // edge cases
    if (money == null || money.length == 0) {
        return 0;
    }
    // create memo table
    int[] memo = new int[money.length + 1];
    // init base cases
    memo[0] = 0;
    memo[1] = money[0];
    // topo order
    for (int i = 2; i < memo.length; i++) {
        memo[i] = Math.max(memo[i-1], memo[i-2] + money[i-1]);
    }
    // answer
    return memo[memo.length-1];
}

Notice the recurrence only uses memo[i-1] and memo[i-2]. So we can just use two variables to replace the memo table as long as we update both of them inside the for loop.

Updated Code

public int rob(int[] money) {
    // edge cases
    if (money == null || money.length == 0) {
        return 0;
    }
    // create memo vars & init base cases
    int last = 0;
    int current = money[0];
    // topo order
    for (int i = 1; i < money.length; i++) {
        int temp = current;
        current = Math.max(current, last + money[i]);
        last = temp;
    }
    // answer
    return current;
}

Time & Space Complexity

Time - O(n) Space - O(n) (can be reduced to O(1))

House Robber II (LC.213)

Adding an extra constraint: you can only rob either the first house or the last house. The neighborhood is a circle.

Approach

func rob2(int[] money)
    int earning1 = rob(money[1:n]) // rob from 2nd house to the last one
    int earning2 = rob(money[0:n-1]) // rob from 1st house to the second last one
    return Math.max(earning1, earning2)
end func