动态归化. 打家劫舍问题

动态规划在打家劫舍问题中的应用

打家劫舍问题是一类经典的动态规划问题，主要考察如何在满足特定约束条件下最大化收益。以下是针对不同打家劫舍问题的详细解答：

1. 打家劫舍 I（LeetCode 198）

问题描述：给定一个非负整数数组，表示每个房屋中的金额。不能同时抢劫相邻的房屋，求能抢劫的最大金额。

方法一：深度优先遍历（记忆化搜索）

将问题抽象为二叉树，每个节点有两个选择：偷或不偷。使用记忆化搜索避免重复计算。

class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) memo = [-1] * n def dfs(i): if i >= n: return 0 if memo[i] != -1: return memo[i] left = dfs(i + 1) right = dfs(i + 2) memo[i] = max(left, right + nums[i]) return memo[i] return dfs(0)

方法二：动态规划

使用动态规划数组 dp，其中 dp[i] 表示前 i 个房屋能抢劫的最大金额。

class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] if n == 2: return max(nums[0], nums[1]) dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) return dp[n - 1]2. 打家劫舍 II（LeetCode 213）

问题描述：房屋围成一圈，即第一个和最后一个房屋相邻。不能同时抢劫相邻的房屋。

方法：将问题拆分为两个子问题：

不抢劫第一个房屋，抢劫剩余房屋。
不抢劫最后一个房屋，抢劫剩余房屋。取两者中的最大值。

class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] def rob_dp(nums_): n = len(nums_) if n == 1: return nums_[0] if n == 2: return max(nums_[0], nums_[1]) dp = [0] * n dp[0] = nums_[0] dp[1] = max(nums_[0], nums_[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + nums_[i]) return dp[n - 1] return max(rob_dp(nums[:-1]), rob_dp(nums[1:]))3. 打家劫舍 III（LeetCode 337）

问题描述：房屋排列成二叉树，不能同时抢劫直接相连的两个房屋。求能抢劫的最大金额。

方法：使用深度优先遍历（DFS），对于每个节点，返回两个值：

不抢劫当前节点时，子树能抢劫的最大金额。
抢劫当前节点时，子树能抢劫的最大金额。

class Solution: def rob(self, root: Optional[TreeNode]) -> int: def dfs(root): if not root: return [0, 0] left = dfs(root.left) right = dfs(root.right) res = [0, 0] res[0] = max(left[0], left[1]) + max(right[0], right[1]) res[1] = left[0] + right[0] + root.val return res res = dfs(root) return max(res[0], res[1])总结

打家劫舍 I：使用动态规划或记忆化搜索，避免抢劫相邻房屋。
打家劫舍 II：将环形问题拆分为两个线性问题，分别求解后取最大值。
打家劫舍 III：使用DFS遍历二叉树，对于每个节点返回抢劫和不抢劫两种情况的最大值。

这些方法均基于动态规划思想，通过合理定义状态和状态转移方程，高效解决问题。

您可能感兴趣问答

Collapsible

热门标签

热点问答