House Robber
最近炒币炒疯了，每天早上起来就开始看market cap，看各种ICO项目和团队，一看就五六个小时过去了，比维基百科还上瘾。是时候收收心好好刷题了
动态规划的定义 & 性质
198. House Robber
题本身不难，Easy 难度。
先从 Top-Down 的角度来想，如果我们定义 maxProfit(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.
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] f = new int[nums.length + 1];
f[0] = 0;
f[1] = nums[0];
for (int i = 2; i <= nums.length; ++i) {
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
}
return f[nums.length];
}
}
仔细注意上面代码中的写法，因为我们定义的动态数组是：抢劫前n个房子，获得的总profit为f[n]，所以在for循环中我们要走到nums.length这一步，在下标方面也有些许注意的地方，i < = nums.length，像是这样，在动态规划中走到原数组的边界外一位，是很常见的一种操作，所以在创建dp动规方程的时候，数组就需要开大一格。
另一种做法是把动态方程的定义改成，抢劫到第n的房子的时候，总收益为f[n]，注意这个时候我们要考虑只有1个或者2个房子的情况，进行特判，不然会出现越界的错误。当然我还是喜欢上面那种写法。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0], nums[1]);
int[] f = new int[nums.length + 1];
f[0] = nums[0];
f[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; ++i) {
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]);
}
return f[nums.length - 1];
}
}
此题的另外考点在于空间的优化。因为每一个 size = n 的问题只和前面的 2 个子问题相关，我们显然不需要存储所有的状态，而可以用滚动数组优化空间占用。 滚动数组的简单用法就是模，即对 dp[] 的 index 取 mod，
除数等于需要保存的状态数。
在数组 index % mod 的做法其实相当于做了一个 circular buffer, 使得固定长度的数组收尾相接，依序覆盖。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int[] f = new int[2];
f[0] = 0;
f[1] = nums[0];
for (int i = 2; i <= nums.length; ++i) {
f[i % 2] = Math.max(f[(i - 1) % 2], f[(i - 2) % 2] + nums[i - 1]);
}
return f[nums.length % 2];
}
}
题外话，cicular buffer 很适合用于实现 fixed-size queue，一个 java 实现看一看这个帖子，java底层的queue就是用滚动数组实现的，所以在前面的某个高频题中，我们用滚动数组或者queue都是可以的，空间复杂度相同，因为本来就是一个东西，但你把滚动数组手动写出来会多一些逼格（大概？）。
213. House Robber II
这题考察环形数组中，subproblem 的拆分与覆盖。
数组变成环形之后，就需要考虑首尾相接的问题了~ 理论上说，对于长度为 n 的环形数组，我们现在有了 n 种不同的切分方式，去处理长度为 n 的线性数组。
不过我们不需要考虑所有的可能切分，因为只有相邻元素之间会出现问题。我们的 subproblem 不能再以 size = n 开始 top-down了，因为无法保证正确性； 但是 size = n - 1 的所有 subproblems，一定是正确的。我们只需要考虑，如何拆分 size = n - 1 的 subproblems，并且如何用他们构造出全局最优解。
只需要把环形数组拆分成两个头尾不同的 size = n - 1 的 subproblems 就可以了：
【1, 7, 5, 9, 2】
下面的 subproblem 覆盖了所有不抢最后一座房子的 subproblems；
【(1, 7, 5, 9) 2】
如下的 subproblem 覆盖了所有不抢第一座房子的 subproblems；
【1,(7, 5, 9, 2)】
如果最后的最优解第一座和最后一座房子都不抢，也一定会被包含在左右两个 subproblem 的范围内，因为其 size = n - 2;
【1, (7, 5, 9), 2】
由于我们不能同时抢第第一和最后一座房子，上面两个 overlap subproblem 一定覆盖了所有子问题的最优解，并且符合全局最优解的 optimal substructure，保证了算法的正确性。
易错点： 后半段数组的 index offset，合理的处置是用完全一样的 for loop，只在实际取元素的时候做 nums[i + 1]，不然计算后半段以 i = 3 开始时，覆盖的 dp[] 位置是错的。
这一点我觉得也很容易理解，所有nums下标都与start相关，而不是与f[]动态数组有关。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
if(nums.length == 2) return Math.max(nums[0], nums[1]);
int left = helper(nums, 0);
int right = helper(nums, 1);
return Math.max(left, right);
}
private int helper(int[] nums, int start) {
int[] f = new int[nums.length];
f[0] = nums[start];
f[1] = Math.max(nums[start], nums[start + 1]);
for (int i = 2; i < nums.length - 1; ++i) {
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i + start]);
}
return f[nums.length - 2];
}
}
空间优化，滚动数组的写法相同。
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
if(nums.length == 2) return Math.max(nums[0], nums[1]);
int left = helper(nums, 0);
int right = helper(nums, 1);
return Math.max(left, right);
}
private int helper(int[] nums, int start) {
int[] f = new int[2];
f[0] = nums[start];
f[1] = Math.max(nums[start], nums[start + 1]);
for (int i = 2; i < nums.length - 1; ++i) {
f[i % 2] = Math.max(f[(i - 1) % 2], f[(i - 2) % 2] + nums[i + start]);
}
return f[(nums.length - 2) % 2];
}
}
337. House Robber III
发现没有，@dietpepsi 这个b加的问题都挺难的，全是那种奇怪刁钻的问题。妈个蛋
回顾下这章一开始对动态规划的总结，可以很容易看出来，这题的左右子树 subproblem 是 disjoint.
因此这道题只有 optimal substructure，而没有 overlap subproblems.
这道题只有 DP 的一个性质： optimal substructure，即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见，因此遇到一个问题的时候，要注意按照其性质属性仔细辨别正确解法。
在 Tree 上做递归的时候返回顺序已然是 bottom-up，相对于每一个节点，并没有重复计算，也没有 overlap subproblems，因此这只是一个正常的递归搜索问题，而不需要依赖 DP 进行优化。
dfs 时间复杂度已经是 O(n) , n = # of nodes
public class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
int leftLvl = 0, rightLvl = 0;
int subleftLvl = 0, subrightLvl = 0;
if(root.left != null){
leftLvl = rob(root.left);
subleftLvl = rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){
rightLvl = rob(root.right);
subrightLvl = rob(root.right.left) + rob(root.right.right);
}
return Math.max(subleftLvl + subrightLvl + root.val, leftLvl + rightLvl);
}
}
leetcode论坛一个答案解释的挺好的：
Apparently the analyses above suggest a recursive solution. And for recursion, it's always worthwhile figuring out the 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 the two "child-subtrees" (root.left, root.right). We only need to choose the scenario which yields the larger amount of money.