代码随想录算法训练营第四十七天|198. 打家劫舍、213. 打家劫舍 II、337. 打家劫舍 III。
198. 打家劫舍
题目链接：打家劫舍
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
解题思路：
1、确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2、确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3、dp数组如何初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
4、确定遍历顺序
dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！
5、举例推导dp数组
代码实现：
class Solution {public int rob(int[] nums) {if (nums == null)return 0;if (nums.length == 1)return nums[0];int len = nums.length;int[] dp = new int[len];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < len; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[len - 1];}
}
213. 打家劫舍 II
题目链接：打家劫舍 II
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
解题思路：
此题是 198. 打家劫舍 的拓展版： 唯一的区别是此题中的房间是 环状排列 的（即首尾相接），而 198. 题中的房间是 单排排列 的；而这也是此题的难点。
环状排列意味着第一个房子和最后一个房子中 只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个 单排排列房间 子问题：
在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]nums[1:]），最大金额是p1
在不偷窃最后一个房子的情况下（即 nums[:n−1]nums[:n-1]nums[:n−1]），最大金额是 p2
综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)max(p1,p2)max(p1,p2) 。
代码实现：
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0)return 0;int len = nums.length;if (len == 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x = 0, y = 0, z = 0;for (int i = start; i < end; i++) {y = z;z = Math.max(y, x + nums[i]);x = y;}return z;}
}
337. 打家劫舍 III
题目链接：打家劫舍 III
题目描述：
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
解题思路：
每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷
当前节点选择偷时，那么两个孩子节点就不能选择偷了
当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系)
我们使用一个大小为 2 的数组来表示 int[] res = new int[2] 0 代表不偷，1 代表偷
任何一个节点能偷到的最大钱的状态可以定义为
当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
代码实现：
class Solution {public int rob(TreeNode root) {int[] result = robInternal(root);return Math.max(result[0], result[1]);}public int[] robInternal(TreeNode root) {if (root == null)return new int[2];int[] result = new int[2];int[] left = robInternal(root.left);int[] right = robInternal(root.right);result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);result[1] = left[0] + right[0] + root.val;return result;}
}