目录
打家劫舍
力扣上打家劫舍相关的题目如下：
| 序号 | 题目 | 区别 |
|---|---|---|
| 1 | 198. 打家劫舍 | 不能偷窃相邻的房间 |
| 2 | 213. 打家劫舍 II | 房间连成环 |
| 3 | 337. 打家劫舍 III | 房间组成一棵二叉树 |
应用
应用1：Leetcode.198
题目
分析
设 \(dp[i]\) 表示前 \(i\) 个房间能获取的最大金额，设房间数量为 \(n\)，那么， \(0 \le i \le n\)。
边界条件
当只有一个房间时，显然最大收益，就是选择偷窃该房间所所得的收益，即
\[dp[0] = nums[0] \]状态转移
当 \(i \ge 1\) 时，对于第 \(i\) 个房间\(nums[i]\)，有两种选择：
- 不选择偷窃这个房间，那么，可以获取的最大金额就是 \(dp[i - 1]\)；
- 选择偷窃这个房间，那么，可以获取的最大金额就是 \(dp[i - 2] + nums[i]\);
综上，能获取的最大金额就是上述两种情况的最大值，即状态转移方程：
\[dp[i] = \max(dp[i - 1], \ dp[i - 2] + nums[i]), \quad i \ge 1 \]代码实现
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[n - 1]
对其压缩状态，优化后的实现：
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
a = nums[0]
b = max(nums[1], nums[0])
c = b
for i in range(2, n):
c = max(b, a + nums[i])
a = b
b = c
return c
应用2：Leetcode.213
题目
分析
设 \(dp[i]\) 表示前 \(i\) 个房间能获取的最大金额，设房间数量为 \(n\)。
题目中的限制条件，可以等价于：
- 若偷窃了第一个房间，就不能偷窃最后一个房间，即可以偷窃房间的范围为：\(nums[0], \ \cdots, \ nums[n -2]\)；
- 若没有偷窃第一个房间，就可以偷窃最后一个房间，即可以偷窃房间的范围为：\(nums[1], \ \cdots, \ nums[n -1]\)。
因此，我们只需要针对上述两种情况，利用前面一道题的分析结果，分别计算两种情况的最大值，最后，再选择最优解即可。
代码实现
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
return max(self.rob_money(nums[1:]), self.rob_money(nums[:n - 1]))
def rob_money(self, nums:List[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[n - 1]
应用3：Leetcode.337
题目
分析
由于，我们一般采用递归的方式遍历一棵树，所以，求解树上的动态规划时，通常采用自顶向下的方式，通过分解子问题的方式求解。
对于任意一个节点，我们注意到，它都会有两种状态：选择当前节点或者不选择节点，所以，递归的过程中，为了表示两种状态，我们定一个函数 do_rob(node: TreeNode)，它返回一个元组 (profit1, profit2)表示对于节点 \(node\) 可以获取的收益，其中元组的值 \(profit1\)、\(profit2\) 分别表示选择该节点的最大收益和不选择该节点的最大收益。
对于任意一个节点 \(node\)，我们都有两种选择：选择当前节点或者不选择节点，因此:
- 选择当前节点，那么收益就是当前节点的值，加上不选择两个子节点的收益；
- 不选当前节点，那么收益就是两个子节点的收益之和，其中，子节点的最大收益等于选择子节点的收益和不选择子节点的收益的最大值；
这里，我们选择通过后序遍历的方式计算每个节点收益，即在离开当前节点的时候，计算当前节点的收益。
代码实现
class Solution:
def rob(self, root: TreeNode) -> int:
if not root:
return 0
profit = self.do_rob(root)
return max(profit[0], profit[1])
def do_rob(self, root: TreeNode) -> Tuple[int, int]:
if not root:
return 0, 0
# 左侧子树的收益
left = self.do_rob(root.left)
# 右侧子树的收益
right = self.do_rob(root.right)
# 选择当前节点的最大收益：选择了当前节点，左右节点都不能选择
profit1 = root.val + left[1] + right[1]
# 不选择当前节点的最大收益：左右子节点的最大收益之和
profit2 = max(left[0], left[1]) + max(right[0], right[1])
return profit1, profit2