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))
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
