198. House Robbery & 213. House Robbery II & 337. House Robbery III
问题1
就是说有一排房子，每个里面都有一定价值的财物，有一个小偷要依次路过每个房子偷东西，但是不能两个房子连着偷不然就会触发报警。 那么在这种限制下，能够偷到的最大价值是多少。
解析1
这个题举个例子，从第一栋房子的话，小偷的选项就有偷或者不偷，这个是随机的。但是对于下一栋房子，是有限制的，根据题意，不能连着偷。所以如果前面的偷了紧接着后面的这个就一定不可偷；如果前面的没有偷，那么后面紧跟的这个就没有限制，就可以选择偷或者不偷。依次往后的房子都遵循此规则。
从描述中可以看出，本次的偷盗的收获结果就是根据之前的偷的结果，和本间房子里财物的价值决定的。这是具有子问题性质的。所以可以试着用动态规划来做。
首先依据最终要求的结果定义状态，那就是最终的结果是dp[n], n就是最后一个房子的index。另外我们并不能确定最后一栋房子是否被偷，所以我们可以再给状态做一个分类，dp[i][0] & dp[i][1], 第二个维度为0表示没被偷，第二个维度为1表示被偷了。最终在通过最后一栋房子后计算最后一个房子被偷与没被偷之后的最大值，即我们最终所求。
初始化，第一栋房子没被偷那么dp[0][0] = 0， 第一栋房子被偷，则dp[0][1] = nums[0]。
转移公式。 根据我们的定义，分没被偷和被偷两种情况来讨论。当前房子不偷，那么他的结果可以由之前房子没被偷或者被偷的结果来推导。dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);，当前房子被偷，那么此时小偷的获得最大的价值只能是根据前面的房子没被偷的情况来推导，dp[i][1] = dp[i - 1][0]。
代码1
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp[0][0] = 0;
int dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0]
}
return Math.max(dp[i][0], dp[i][1]);
}
}
优化1
根据之前的代码，可以看出当次的状态结果只跟上次有关，所以我们只需要保留之前的一次的结果即可。所以小口诀就是：二维化一维，一维化固定。因为0和1表示的是偷盗状态只有两种，所以可以被我们直接展开。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp_0 = 0;
int dp_1 = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
return Math.max(dp_0, dp_1);
}
}
问题2
这个题说是有个环，所以我们需要考虑第一个和最后一个房子偷盗情况的制约。因为之前从第一个开始，他前面什么也没有，所以偷与不偷都是可选的，但是现在如果房子成环，那么如果第一个房子被偷的话，那么他前一个（就是最后一个）房子一定不可以被偷；如果他没被偷，他前面的房子就没限制。
解析2
这个题就是将偷第一个和不偷第一个房子分类讨论即可。不偷第一个房子，那么对于最后一个（即第一个的前一个）房子是没有限制的；但是偷了第一个，最后一个一定不可以偷，所以最后的结果就不能是偷与不偷的情况取最大值，而只能是不偷的情况的值。
代码2
House Rebbery一的代码分类即可。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// not steal first
int res1 = 0;
int dp_0 = 0; // 不偷第一个的话，那么初始化的第一个结果就一定是0
int dp_1 = 0; // 不偷第一个的话，那么初始化的第一个结果就一定是0
for (int i = 1; i < nums.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
res1 = Math.max(dp_0, dp_1);
// steal first
int res2 = 0;
dp_0 = nums[0]; // 偷第一个的话，那么初始化的偷完第一栋房子的结果就一定是1
dp_1 = nums[0]; // 偷第一个的话，那么初始化的偷完第一栋房子的结果就一定是1
for (int i = 1; i < nums.length; i++) {
if (i == 1) {
continue;
}
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
res2 = dp_0;
return Math.max(res1, res2);
}
}
问题3
还是这个问题，房子的分布从第一题的线段变成环到现在变成二叉树了。同样的限制不能连着偷。问能够偷到的最大价值是多少。
解析3
这个题思路和第一题是一样的。但是最后没有想出来代码怎么去构造。以下给出的是参考答案的构造方法，使用了一些递归的小技巧。此处可以看到二叉树后续遍历的影子。
一般这种情况我们需要左边的结果和右边的结果作为后续步骤的一个变量，那么我们需要先遍历取求取结果后再对当前节点进行操作。同样的转移公式，结果是偷与不偷当前的节点的最大值。
当前节点不偷，那么它的结果源于左孩子（偷或不偷的综合结果）和右孩子的结果（偷或不偷的综合结果）的和；当前的节点偷，那么它的结果就是左右孩子不偷的结果的和，加上当前节点的值。
代码3
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}
private int[] helper(TreeNode root) {
int[] res = new int[2];
if (root == null) {
return res;
}
int[] left = helper(root.left);
int[] right = helper(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
代码4
其实根据我之前的一些提交记录来看，还有一种思想类似但是写出来完全不一样的代码方式。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
int val = 0;
// left grandsons' results
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
// right grandsons' results
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
// choose from steal current node and not rob current node
return Math.max(val + root.val, rob(root.left) + rob(root.right));
}
}
这个写法很巧妙，利用递归隐藏了很多复杂的东西，按照题意把一个节点的当前的选择写出来即可。这道题的代码就是，我也是从偷与不偷当前节点的结果里面选。偷当前节点的话他的左孩子和右孩子（如果有的话）都不能偷，那就是左边的孙子偷与不偷的结果和右边的孙子偷与不偷的结果之和加上他当前的值；不偷就是他的左右孩子的结果之和。最后两种比较取最大值即可。妙啊。
Question 1
It means that there is a row of houses, each with a certain value of belongings inside, and a thief has to pass by each house in turn to steal something, but not two houses in a row or else the alarm will be triggered. So what is the maximum value that can be stolen under this restriction.
Solution 1
This question is an example, from the first house, the thief's options are to steal or not to steal, this is random. But for the next house, there is a limit, according to the question, can not be stolen in a row. So if the front steal immediately after this one must not steal; if the front did not steal, then the immediately following this one has no restrictions, so you can choose to steal or not steal. This rule is followed by the next house in order.
As you can see from the description, the result of the current theft is based on the result of the previous theft and the value of the belongings in the house. This is of sub-problem nature. So you can try to do it with dynamic programming.
First define state based on the final required result, that is the final result is dp[n], n is the index of the last house. in addition we are not sure whether the last house was stolen or not, so we can make another classification for the state, dp[i][0] & dp[i][1], the second dimension is 0 means it was not stolen, the second dimension is 1 indicates that it was stolen. Eventually after passing the last house the maximum value after the last house is stolen and not stolen is calculated, which is what we end up with.
Initialization, the first house is not stolen then dp[0][0] = 0, the first house is stolen then dp[0][1] = nums[0].
** Transfer formula. ** According to our definition, it is discussed in two cases: not stolen and stolen. The current house is not stolen, then his result can be deduced from the result of the previous house not stolen or stolen. dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);, the current house is stolen, then at this point the thief's get the maximum value can only be derived from the previous house not stolen, dp[i][1] = dp[i - 1][0].
Code 1
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp[0][0] = 0;
int dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0]
}
return Math.max(dp[i][0], dp[i][1]);
}
}
Optimization 1
According to the previous code, we can see that the current state result is only related to the last time, so we only need to keep the result of the previous one. So the little mnemonic is: two-dimensional to one-dimensional, one-dimensional to fixed. Because 0 and 1 indicate that there are only two kinds of theft states, so they can be expanded by us directly.
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int dp_0 = 0;
int dp_1 = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
return Math.max(dp_0, dp_1);
}
}
Problem 2
This question says that there is a ring, so we need to consider the constraints of the first and last house theft situation. Because before, starting with the first one, there was nothing in front of him, so stealing or not stealing was optional, but now if the houses are in a ring, then if the first house is stolen, then the house before him (which is the last one) must not be stolen; if he is not stolen, the house before him is not constrained.
Solution 2
This question is to classify the discussion between stealing the first house and not stealing the first house. If you don't steal the first house, then there is no restriction on the last (i.e., the one before the first) house; but if you steal the first one, the last one must not be stolen, so the final result can't be the maximum value of the case of stealing or not stealing, but only the value of the case of not stealing.
Code 2
House Rebbery I code classification can be.
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// not steal first
int res1 = 0;
int dp_0 = 0; // not steal the first, then the first result of the initialization must be 0
int dp_1 = 0; // not steal first, then the first result of the initialization must be 0
for (int i = 1; i < nums.length; i++) {
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
res1 = Math.max(dp_0, dp_1);
// steal first
int res2 = 0;
dp_0 = nums[0]; // if you steal the first one, then the initialized result after stealing the first house must be 1
dp_1 = nums[0]; // If you steal the first one, then the initialized result of stealing the first house must be 1
for (int i = 1; i < nums.length; i++) {
if (i == 1) {
continue;
}
int temp = dp_0;
dp_0 = Math.max(dp_0, dp_1);
dp_1 = temp + nums[i];
}
res2 = dp_0;
return Math.max(res1, res2);
}
}
Problem 3
Still the same problem, the distribution of houses has changed from a line segment into a ring in the first problem to a binary tree now. The same restriction cannot be stolen in a row. Ask what is the maximum value that can be stolen.
Solution 3
The idea of this question is the same as the first one. But in the end, I didn't figure out how to construct the code. The following is the construction method of the reference answer, using some recursive tricks. Here you can see the shadow of the subsequent traversal of the binary tree.
Generally this situation we need the result on the left and the result on the right as a variable in the subsequent steps, then we need to traverse first to get the result and then operate on the current node. The same transfer formula, the result is the maximum value of the node that steals and does not steal the current node.
The current node does not steal, then its result stems from the sum of the results of the left child (the combined result of steal or not steal) and the right child (the combined result of steal or not steal); the current node steals, then its result is the sum of the results of the left and right children not steal, plus the value of the current node.
Code 3
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0], res[1]);
}
private int[] helper(TreeNode root) {
int[] res = new int[2];
if (root == null) {
return res;
}
int[] left = helper(root.left);
int[] right = helper(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
Code 4
Actually, based on some of my previous commits, there is another way of writing code that is similar in thought but completely different.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
int val = 0;
// left grandsons' results
if (root.left ! = null) {
val += rob(root.left.left) + rob(root.left.right);
}
// right grandsons' results
if (root.right ! = null) {
val += rob(root.right.left) + rob(root.right.right);
}
// choose from steal current node and not rob current node
return Math.max(val + root.val, rob(root.left) + rob(root.right));
}
}
This is a clever way of writing, using recursion to hide a lot of complexity, just write out the current choice of a node as the question suggests. The code for this problem is that I also choose from the result of stealing or not stealing the current node. Steal the current node, his left child and right child (if any) can not steal, that is, the left grandson to steal and not steal the result and the right grandson to steal and not steal the result of the sum of his current value; not to steal is the sum of the results of his left and right children. The last two comparisons take the maximum value. Wonderful.