House Robber
House Robber
题本身不难，Easy难度。
先从Top-Down的角度来想，如我们定义maxPorfit(n)为长度为n的array中所能得到的最大利益的话，不难看出在计算maxProfit(n)的时候，它的值纸盒前两个subproblem相关，即maxProfit(n - 1)和maxProfit(n - 2)。
由此我们发现DP的第一个性质: overlap subproblems.
同时如果maxProfit(n - 1)和maxProfit(n - 2)都是其对应子问题的最优解的话，我们就可以只利用这两个字问题的solution，嫁对对当前元素的判断，构造出maxProfit(n)的最优解。
因此我们满足DP的正确性质: optimal substructure.
此题的另外考点在于空间优化。因为每一个size = n的问题纸盒前面2个子问题相关，我们显然不需要存储所有的状态，而可以用滚动数组优化空间占用。滚动数组的简单用法就是取模。即对dp[]的index取mod，除数等于需要保存的状态数。
在数组index % mod的做法其实相当于做了一个circular buffer，使得固定长度的数组首位相接，依序覆盖。
题外话，circular buffer很适合用于实现fixed-size queue，一个java实现看一看这个帖子
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
} else if (nums.length == 0) {
return Math.max(nums[0], nums[1]);
}
int[] dp = new int[2];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i % 2] = Math.max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i]);
}
return dp[(nums.length - 1) % 2];
}
}
House Robber II
这题考察环形数组中，subproblem的拆分与覆盖。
数组变成环形之后，就需要考虑首尾相接的问题了~理论上说，对于长度为n的环形数组，我们现在有了n种不同切分方式，去处理长度为n的线性数组。
不过我们不需要考虑所有的可能切分，因为向零元素之间会出现问题。我们的subproblem不能再以size = n开始top-down了，因为无法保证正确性；但是size = n - 1的所有subproblem一定是正确的。我们只需要考虑，如何拆分size = n - 1的subproblem， 并且如果用他们构造出全局的最优解。
只需要把环形拆分成两个头尾不同的size = n - 1的subproblem就可以了：
[1, 7, 5, 9, 2]
下面的subproblem覆盖了所有不抢最后一座房子的subproblem；
[(1, 7, 5, 9,) 2]
如下的subproblem覆盖了所有不抢第一座房子的subproblem；
[1, (7, 5, 9, 2)]
由于我们不能同时抢第一个和最后一个房子，上面两个overlap subproblem一定覆盖了所有子问题的最优解，并且符合全局最优解的optimal substructure，保证了算法的正确性。
易错点：后半段数组的index offset，合理的处置是完全一样的for loop，只在实际取元素的时候做nums[i + 1]，不然计算后半段以i = 3开始时，覆盖的dp[]位置是错的。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
} else if (nums.length == 1) {
return nums[0];
}
return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));
}
private int helper(int[] nums, int start, int end) {
if (start == end) {
return nums[start];
} else if (start + 1 == end) {
return Math.max(nums[start], nums[start + 1]);
}
int[] dp = new int[2];
dp[0] = nums[start];
dp[1] = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[(i - start) % 2] = Math.max(dp[(i - start - 1) % 2], dp[(i - start - 2) % 2] + nums[i]);
}
return dp[(end - start) % 2];
}
}
House Robber III
discussion里很好的帖子 https://discuss.leetcode.com/topic/39834/step-by-step-tackling-of-the-problem
Let's define the function rob(root) which will return the maximum amount of money that we can rob for the binary tree rooted at root; the key no is to construct the solution to the original problem from solutions to its subproblems, i.e., how to get rob(root) from rob(root.left), rob(root.right), ...etc.
Apparently the analyses above suggests a recursive solution. And for recursion, it's always worthwhile figuring out following two properties:
- Termination condition: when do we know the answer to rob(root) without any calculation? Of course when the tree is empty -- we've got nothing to rob so the amount of money is zero.
- Recurrence relation: i.e., how to get rob(root) from rob(root.left), rob(root.right), ... etc. From the point of view of the tree root, there are only two scenarios at the end: root is robbed or is not. If it is, due to the constraint that "we cannot rob any two directly-linked houses", the next level of subtrees that are available would be the four "grandchild-subtrees" (root.left.left, root.left.right, root.right.left, root.right.right). However if root is not robbed, the next level of available subtrees would just be two "child-subtrees" (root.left, root.right). We only need to choose the scenario which yields the larger amount of money.
public class Solution {
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
int sum = root.val;
if (root.left != null) {
sum += rob(root.left.left);
sum += rob(root.left.right);
}
if (root.right != null) {
sum += rob(root.right.left);
sum += rob(root.right.right);
}
sum = Math.max(sum, rob(root.left) + rob(root.right));
return sum;
}
}
Think one step further In step I, we only considered the aspect of "optimal substructure", but think little about the possibilities of overlapping of the subproblems. For example, to obtain rob(root), we need rob(root.left), rob(root.right), rob(root.left.left), rob(root.left.right), rob(root.right.left), rob(root.right.right); but to get rob(root.left), we also need rob(root.left.left), rob(root.left.right), similarly for rob(root.right). The naive solution above computed these subproblems repeatedly, which resulted in bad time performance. Now if you recall the two conditions for dynamic programming: “optimal substructure” + "overlapping of subproblems"，we actually have a DP problem. A naive way to implement DP here is to use a hash map to record the results for visited subtrees.
public class Solution {
public int rob(TreeNode root) {
Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
return helper(root, map);
}
private int helper(TreeNode root, Map<TreeNode, Integer> map) {
if (root == null) {
return 0;
} else if (map.containsKey(root)) {
return map.get(root);
}
int sum = root.val;
if (root.left != null) {
sum += helper(root.left.left, map);
sum += helper(root.left.right, map);
}
if (root.right != null) {
sum += helper(root.right.left, map);
sum += helper(root.right.right, map);
}
sum = Math.max(sum, helper(root.left, map) + helper(root.right, map));
map.put(root, sum);
return sum;
}
}
Step III --- Think one step back
In stepI, we defined our problem asrob(root), which will yield the maximum amount of money that can be robbed of the binary tree rooted atroot. This leads to the DP problem summarized in stepII.
Now let's take one step back and ask why we have overlapping subproblems. If you trace all the way back to the beginning, you'll find the answer lies in the way how we have definedrob(root). As I mentioned, for each tree root, there are two scenarios: it is robbed or is not.rob(root)does not distinguish between these two cases, so "information is lost as the recursion goes deeper and deeper", which results in repeated subproblems.
If we were able to maintain the information about the two scenarios for each tree root, let's see how it plays out. Redefinerob(root)as a new function which will return an array of two elements, the first element of which denotes the maximum amount of money that can be robbed ifrootis not robbed, while the second element signifies the maximum amount of money robbed if it is robbed.
Let's relaterob(root)torob(root.left)androb(root.right)..., etc. For the 1st element ofrob(root), we only need to sum up the larger elements ofrob(root.left)androb(root.right), respectively, sincerootis not robbed and we are free to rob its left and right subtrees. For the 2nd element ofrob(root), however, we only need to add up the 1st elements ofrob(root.left)androb(root.right), respectively, plus the value robbed fromrootitself, since in this case it's guaranteed that we cannot rob the nodes ofroot.leftandroot.right.
As you can see, by keeping track of the information of both scenarios, we decoupled the subproblems and the solution essentially boiled down to a greedy one.
实际就是一个postorder traversal, O(n)的解法，且每个node只访问一次。
public class Solution {
public int rob(TreeNode root) {
int[] result = helper(root);
// result[0]: max profit when root is not robbed, result[1]: max profit when root is robbed
return Math.max(result[0], result[1]);
}
private int[] helper(TreeNode root) {
if (root == null) {
return new int[2];
}
int[] result = new int[2];
int[] left = helper(root.left);
int[] right = helper(root.right);
result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
result[1] = root.val + left[0] + right[0];
return result;
}
}