打家劫舍 I
简单说就是相邻房间不能偷取，偷取下标为 i 的房间时，i – 1 的房间不能偷，只有 i – 2 （或 i + 2）的房间可以偷。
由于有这样的状态，自然而然想到了动规求解。
1. 确定 dp 数组的含义：
包含下标为 i 以及之前的房间偷窃的最大金额为 dp[i]
2. 确定递推公式：
遍历到下标为 i 的房间时，有两种状态：
- 偷取 i ，则为上一个偷取房间的状态+房间 i 的金额 ：dp[i] = dp[i – 2] + nums[i]
- 不偷取 i ，说明 i – 1 已经偷取过，则直接返回上一个房间的状态：dp[i] = dp[i – 1]
综上，dp[i] = max(dp[i – 1], dp[i – 2] + nums[i])
3. 初始化：
- 对于 dp[0]，金额只能是 nums[0]
- 对于 dp[1]，金额为 nums[0] 和 nums[1] 中的最大值，这样才能选出最大的金额
4. 确定遍历顺序：
dp[i] 是根据dp[i – 2] 和 dp[i – 1] 推导出来的，那么一定是从前到后遍历
代码如下：
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
打家劫舍 II
这道题在上一题的基础上，变成了环形数组。除了上一题的条件，增加了首尾相邻的房间也不能偷取的条件。
这道题很容易掉进处理环形数组的陷阱里，其实分情况就可以了（借用代码随想录的图）：
这里是考虑！并不是一定包含尾元素，比如情况三，取 1 和 3 就是最大的情况。
然后我们可以发现，情况二和情况三包含了情况一，所以只关注这两种情况就可以。
分析到这里，给出代码：
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int res1 = robAction(nums, 0, nums.length - 2);
int res2 = robAction(nums, 1, nums.length - 1);
return Math.max(res1, res2);
}
public int robAction(int[] nums, int start, int end) {
if (start == end) return nums[start];
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
}
打家劫舍 III
这道题算是树形dp的入门题目，因为是在树上进行状态转移。
对于一个节点，选或不选的状态是由它的孩子节点决定的，这显然会提醒我们使用后序遍历。
如下图所示，从底层的叶子节点开始，每一个节点都分为了 选/不选 的两种状态值，那么向上看，他们的父节点也具有 选/不选 的两种状态值，而父节点的状态值显然是根据孩子节点得出的，这是更直观的理解。
以根节点 2 为例：
- 如果要选取 2 ，那么他的两个孩子节点就不能选取，只选取根节点的节点值
- 如果不选取 2 ，那么就要选取两个孩子节点各自最大状态值的和
这里可以使用一个长度为2的数组，记录每个节点偷与不偷所得到的的最大金钱。下标0，我们认定为选取当前节点得到的金额；下标1，我们认定为不选取当前节点得到的金额。
代码如下：
class Solution {
public int rob(TreeNode root) {
int[] res = robAction(root);
return Math.max(res[0], res[1]);
}
// 长度为2的数组，0：偷，1：不偷
public int[] robAction(TreeNode node) {
if (node == null) { //递归边界
// 空节点，没有孩子
return new int[]{0, 0};
}
int[] left = robAction(node.left); // 递归左子树
int[] right = robAction(node.right); // 递归右子树
// 选此节点 则不选叶子节点
int rob = left[1] + right[1] + node.val;
// 不选此节点，选叶子节点
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{rob, notRob};
}
}
总结
劫舍系列简单来说就是：数组上连续元素二选一，成环之后连续元素二选一，在树上连续元素二选一，所能得到的最大价值。
