代码随想录算法训练营第三十四天 | 动态规划 Part07

566 字

3 分钟

代码随想录算法训练营第三十四天 | 动态规划 Part07

2025-07-19

算法

动态规划、打家劫舍

/

LeetCode

/

Python

198. 打家劫舍#

LeetCode 198. House Robber

思路分析：#

使用递归 + 记忆化搜索（自顶向下）
dp[i] 表示从第 i 间房子开始偷窃所能获得的最大金额

Python代码：#

1
class Solution:
2
    def rob(self, nums: List[int]) -> int:
3
        # 初始化记忆数组，避免重复计算
4
        self.memo = [-1] * len(nums)
5
        return self.dp(nums, 0)
6

7
    def dp(self, nums, start):
8
        # 递归终止条件：超出数组范围
9
        if start >= len(nums):
10
            return 0
11

12
        # 如果已经计算过，直接返回记忆值
13
        if self.memo[start] != -1:
14
            return self.memo[start]
15

16
        # 决策：偷 or 不偷当前房子
17
        res = max(
18
            self.dp(nums, start + 1),                      # 不偷当前房子
19
            nums[start] + self.dp(nums, start + 2)         # 偷当前房子，然后跳过下一个
20
        )
21

22
        self.memo[start] = res
23
        return res

213. 打家劫舍 II#

LeetCode 213. House Robber II

环形问题 ⇒ 不能同时选择第一个和最后一个
转化为两个线性子问题：
- 情况一：不偷最后一个房子（范围：[0, n-2]）
- 情况二：不偷第一个房子（范围：[1, n-1]）
两者取最大值即可。

1
class Solution:
2
    def rob(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        if n == 1:
5
            return nums[0]
6

7
        # 分两种情况：不包含最后一个 和 不包含第一个
8
        memo1 = [-1] * n
9
        memo2 = [-1] * n
10

11
        return max(
12
            self.dp(nums, 0, n - 2, memo1),    # 偷[0, n-2]
13
            self.dp(nums, 1, n - 1, memo2)     # 偷[1, n-1]
14
        )
15

16
    def dp(self, nums, start, end, memo):
17
        # 边界条件
18
        if start > end:
19
            return 0
20

21
        # 返回记忆值
22
        if memo[start] != -1:
23
            return memo[start]
24

25
        # 决策：偷 or 不偷当前房子
26
        res = max(
27
            self.dp(nums, start + 1, end, memo),                    # 不偷当前房子
28
            nums[start] + self.dp(nums, start + 2, end, memo)       # 偷当前房子
29
        )
30

31
        memo[start] = res
32
        return res

337. 打家劫舍 III#

LeetCode 337. House Robber III

对每个节点做决策：偷 or 不偷
返回值为一个二元组 (不偷该节点的最大值, 偷该节点的最大值)
采用后序遍历递归 + 动态规划（树形DP）

1
class Solution:
2
    def rob(self, root: Optional[TreeNode]) -> int:
3
        # 返回值是一个元组：(不偷当前节点, 偷当前节点)
4
        return max(self.dfs(root))
5

6
    def dfs(self, node):
7
        # 空节点返回 (0, 0)
8
        if not node:
9
            return (0, 0)
10

11
        # 后序遍历左右子树
12
        left = self.dfs(node.left)
13
        right = self.dfs(node.right)
14

15
        # 不偷当前节点：左右子节点可偷可不偷，取最大
16
        not_rob = max(left) + max(right)
17

18
        # 偷当前节点：不能偷左右子节点
19
        rob = node.val + left[0] + right[0]
20

21
        return (not_rob, rob)