[LeetCode] 198. 打家劫舍

本题是一个经典的动态规划问题，旨在计算在不触发警报的情况下，小偷能够偷窃到的最高金额。

方法思路方法一：自顶向下（记忆化递归）

这种方法使用递归来探索所有可能的偷窃路径，并通过记忆化技术来避免重复计算。具体步骤如下：

递归函数定义：定义一个辅助函数 helper(i)，表示从第 i 间房屋开始偷窃能够获得的最大金额。
递归终止条件：如果 i 超出房屋数量，返回 0。
递归关系：对于每间房屋 i，小偷有两个选择：
偷窃当前房屋 i，然后跳过下一间房屋 i+1，即 nums[i] + helper(i + 2)。
不偷窃当前房屋 i，直接考虑下一间房屋 i+1，即 helper(i + 1)。
取这两个选择中的较大值作为 helper(i) 的结果。
记忆化存储：使用 lru_cache 装饰器来缓存已经计算过的结果，避免重复计算。

方法二：自底向上（动态规划）

这种方法通过迭代的方式从底向上构建解，使用一个数组 dp 来存储中间结果。具体步骤如下：

初始化：创建一个长度为 n + 1 的数组 dp，其中 dp[i] 表示偷窃到第 i 间房屋时的最大金额。
基础情况：dp[0] = 0（没有房屋可偷），dp[1] = nums[0]（只有一间房屋时只能偷它）。
状态转移：对于每间房屋 i（从 2 到 n），dp[i] 的值由以下两种情况决定：
偷窃当前房屋 i-1，则不能偷窃前一间房屋 i-2，即 dp[i-2] + nums[i-1]。
不偷窃当前房屋 i-1，则最大金额为 dp[i-1]。
取这两个值中的较大值作为 dp[i]。
结果：dp[n] 即为偷窃到最后一间房屋时的最大金额。

解决代码方法一：自顶向下（记忆化递归）class Solution: def rob(self, nums: List[int]) -> int: import functools n = len(nums) @functools.lru_cache(None) def helper(i): if i >= n: return 0 return max(helper(i + 1), nums[i] + helper(i + 2)) return helper(0)方法二：自底向上（动态规划）class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 dp = [0] * (n + 1) dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) return dp[-1]代码解释

方法一：使用递归函数 helper(i) 来计算从第 i 间房屋开始的最大金额。通过 lru_cache 装饰器缓存中间结果，避免重复计算，提高效率。
方法二：使用动态规划数组 dp 来存储中间结果。dp[i] 表示偷窃到第 i 间房屋时的最大金额，通过状态转移方程 dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) 逐步构建解，最终返回 dp[n]。

这两种方法都能有效地解决问题，方法一通过递归和记忆化技术更直观，而方法二通过迭代和动态规划数组在空间上可能更优。

您可能感兴趣问答

Collapsible

热门标签

热点问答