House Robber I/II/III
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
House Robber III (LC.337)
Now you decide to rob a neighborhood that's more challenging. The neighborhood's structure is a binary tree. The constraint is that you cannot rob two directed linked houses. Return the maximum amount of money you can rob at given neighborhood.
Analysis
Subtree DP =͟͟͞͞•̫͡•ʔ
Firstly, since the tree node is defined to hold only the money value, we have to figure out a way to memoize the partial solutions at each node. A structure like Map<TreeNode, Integer> will work fine. Secondly, the constraint is that we cannot rob two directly linked houses. So which order should we visit the nodes? Either preorder or postorder. (inorder doesn't make sense since cause you can't make a decision on to rob or not to rob base on one child).
Approach
1. define optimal subproblems - by subtree
rob(root) = maximum amount of money you can rob at the subtree starting from root
2. solve by subtree, again 2 options, to rob at root or skip it
rob(root) = Math.max(root.value + rob(root.left.left) + rob(root.left.right) + rob(root.right.left)
+ rob(root.right.right), rob(root.left) + rob(root.right));
3. topo order
from leaf nodes to the root
4. init base cases
if (root == null) return 0
5. answer
return memo.get(root)
Code
public int rob(TreeNode root) {
// edge cases
if (root == null) {
return 0;
}
// create memo table
Map<TreeNode, Integer> memo = new HashMap<>();
// fill in the memo table
robHelper(root, memo);
// answer
return memo.get(root);
}
private int robHelper(TreeNode root, Map<TreeNode, Integer> memo) {
// base case
if (root == null) {
return 0;
}
if (memo.containsKey(root)) {
return memo.get(root);
}
// divide & conquer style
int leftLeftSubtree = 0;
if (root.left != null) {
leftLeftSubtree = robHelper(root.left.left, memo) + robHelper(root.left.right, memo);
}
int rightRightSubtree = 0;
if (root.right != null) {
rightRightSubtree = robHelper(root.right.left, memo) + robHelper(root.right.right, memo);
}
// recurrence
int maxEarning = Math.max(root.val + leftLeftSubtree + rightRightSubtree,
robHelper(root.left, memo) + robHelper(root.right, memo));
// memoization
memo.put(root, maxEarning);
return maxEarning;
}
Time & Space Complexity
Time - O(V)
Space - O(V) since we memoize at every node
Follow Up #3
Can you solve question 3 in in O(1) space?
Analysis
The approach above is essentially recursion and memoization which requires O(#subproblems) space. O(1) space is usually asking for the bottom up approach - tabulation. Before we build this tree bottom up, we need to revisit how we defined the (optimal) subproblems. The way we firstly defined the subproblems is optimal not very efficient. The newly defined subproblems can still overlap with each other (see maxEarning). Instead, we want to distinguish the two possible options - rob and not rob. We want to keep track of them at each node to build this implicit memoization tree bottom up.
Updated Code
class ReturnType {
int rob;
int notRob;
ReturnType(int val1, int val2) {
rob = val1;
notRob = val2;
}
}
public int rob(TreeNode root) {
ReturnType result = robHelper(root);
return Math.max(result.rob, result.notRob);
}
private ReturnType robHelper(TreeNode root) {
// base case
if (root == null) {
return new ReturnType(0, 0);
}
// divide & conquer (post-order traversal)
ReturnType leftSubtree = robHelper(root.left);
ReturnType rightSubtree = robHelper(root.right);
// recurrence & merge
int rob = root.val + leftSubtree.notRob + rightSubtree.notRob;
int notRob = Math.max(leftSubtree.rob, leftSubtree.notRob) +
Math.max(rightSubtree.rob, rightSubtree.notRob);
return new ReturnType(rob, notRob);
}
Time & Space Complexity
Time - O(V) visiting all the nodes
Space - O(1) only keeping track of a tuple of 2 elements (not counting stack frame)
Conclusion
As we have seen from the last question, the challenging part of DP is defining the subproblems in a desirable way. Hopefully, the intuition will be built up after some practices for each paradigm. Here is a quote from the founder of set theory. "To ask the right question is harder than to solve it." -- Georg Cantor