经典题目
简述：小偷计划偷盗沿街相邻的房屋，每个房屋都有一定的现金。制约因素为：如果相邻的房屋在同一晚上被小偷闯入，系统自动报警，求一夜能偷盗的最大金额。
输入：[1,2,3,1] 输出：4 = 1+3 输入：[2,7,9,3,1] 输出：12 = 2 + 9 + 1 # 打家劫舍I def rob(nums): if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] dp = [0] * len(nums) dp[0] = nums[0] dp[1] = max(nums[0], max[1]) for i in range(2, len(nums)): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[-1]
思路
打家劫舍是动态规划的经典问题，按照动态规划五部曲分析如下：
1、确定dp数组以及下标的含义
即dp[i]：考虑下标i以内的房屋，最多可以偷窃的金额为dp[i]
2、确定递推公式
影响dp[i]的因素就是第i房屋偷还是不偷
即偷：dp[i] = dp[i - 2] + nums[i]
不偷：dp[i] = dp[i - 1]
即dp[i]取最大值，递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3、dp数组如何初始化
从递推公式可以看出，初始化数据需要dp[0]和dp[1]
4、确定遍历顺序
易得从前向后遍历
5、举例推导dp数组（举例推导时需要对解题方式有一定轮廓，才能较快解题）
注：链接中图解更方便理解
拓展题型
打家劫舍II
额外约束条件：房屋连成一个环，即第一个房屋和最后一个房屋紧挨着
解题思路：成环条件下考虑三种情况
- 不包含首尾元素
- 只考虑首元素，不考虑尾元素（不一定需要首元素）
- 只考虑尾元素，不考虑首元素（不一定需要尾元素）
可以看出情况2和情况3包含了情况1，即只需要考虑情况2和情况3
# 打家劫舍II # 分两类情况考虑即nums[1:]和nums[:-1]，即 def rob_2(nums): return max(rob(nums[1:]), rob(nums[:-1]))
打家劫舍III
额外约束条件：房屋排列为二叉树状，且只有一个入口为root（离谱~🤣）
解题思路：
- 针对树，首先考虑遍历方式，是前后中序遍历（深度优先搜索）还是层序遍历（广度优先搜索）
- 本题一定是要后序遍历，因为需要通过递归函数的返回值来做下一步计算
# 打家劫舍III class Solution: def rob3(self, root): res = self.rob_tree(root) return max(res[0], res[1]) def rob_tree(self, node): if node is None: return [0, 0] # [偷当前节点的金额, 不偷当前节点的金额] left = self.rob_tree(node.left) right = self.rob_tree(node.right) val1 = node.val + left[1] + right[1] # 偷当前节点，不能偷子节点 val2 = max(left[0], left[1]) + max(right[0], right[1]) # 不偷当前节点，可偷可不偷子节点 return [val1, val2]
