知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 03 - 打家劫舍 ## 题目(LeetCode 198) 不能偷相邻的两家,求能偷到的最大金额。 ``` 输入:[2, 7, 9, 3, 1] 输出:12(偷第 0、2、4 家:2 + 9 + 1 = 12) ``` ## 先搞清楚:约束条件到底是什么 ``` "不能偷相邻的两家"意思是: 如果你偷了第 i 家,那第 i-1 家和第 i+1 家都不能偷 但第 i-2 家可以偷!(中间隔了一家) 举例:[2, 7, 9, 3, 1] 偷第 0 家和第 2 家 → 2 + 9 = 11 ✓(中间隔了第 1 家) 偷第 0 家和第 1 家 → 2 + 7 = 9 ✗(相邻,不行) 偷第 0、2、4 家 → 2 + 9 + 1 = 12 ✓(都不相邻) ``` --- ## 大白话理解 想象你是一个小偷,走到每一家门口,你只有两个选择: ``` 选择 1:偷这家 → 拿到这家的钱,但上一家一定不能偷 → 你的总收入 = 上上家的最大收入 + 这家的钱 选择 2:不偷这家 → 不拿钱,但保留了上一家的最大收入 → 你的总收入 = 上一家的最大收入 你会选哪个?当然是选收入更多的那个! ``` ### 生活类比 ``` 想象你在自助餐厅,菜品排成一排,但有个奇怪的规则: 你拿了一道菜,就不能拿它旁边的菜 菜品价值:[2元, 7元, 9元, 3元, 1元] 你走到每道菜前面,都要做决定:拿还是不拿? 拿了这道,就跳过下一道 不拿这道,下一道可以拿 目标:让拿到的菜总价值最大 ``` --- ## 四步法 ``` 第 1 步:dp[i] = 偷到第 i 家时能获得的最大金额 注意:不是说一定要偷第 i 家,而是"考虑完前 i 家后"的最大金额 第 2 步:dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 偷第 i 家:dp[i-2] + nums[i](跳过第 i-1 家,加上第 i 家的钱) 不偷第 i 家:dp[i-1](和考虑完前 i-1 家一样) 取两者的最大值 第 3 步:dp[0] = nums[0](只有一家,偷它) dp[1] = max(nums[0], nums[1])(两家选一家偷) 第 4 步:从小到大遍历 ``` ### 为什么偷第 i 家时用 dp[i-2] 而不是 dp[i-1]? ``` 因为不能偷相邻的! 如果偷了第 i 家,第 i-1 家一定不能偷 所以你能利用的"之前的最大收入"只能是 dp[i-2](第 i-2 家及之前的最大收入) dp[i-1] 里可能包含了偷第 i-1 家的情况,而第 i-1 家和第 i 家相邻 所以偷第 i 家时不能用 dp[i-1] ``` ### 为什么不偷第 i 家时是 dp[i-1] 而不是 dp[i-2]? ``` 不偷第 i 家,意味着第 i 家对结果没有影响 那最大收入就是"考虑完前 i-1 家"的最大收入,即 dp[i-1] dp[i-1] 已经包含了"偷或不偷第 i-1 家"的最优决策 所以直接用 dp[i-1] 就行 ``` --- ## 决策树:看清每一步的选择 ``` nums = [2, 7, 9, 3, 1] 从第 0 家开始,每家都有"偷"或"跳过"两个选择: 第 0 家(2) / \ 偷(+2) 跳过(+0) / \ 第 1 家(7) 第 1 家(7) [不能偷] / \ | 偷(+7) 跳过(+0) 跳过 / \ | 第 2 家(9) 第 2 家(9) 第 2 家(9) [不能偷] / \ / \ | 偷(+9) 跳过 偷(+9) 跳过 跳过 | | | | | 第 3 家 第 3 家 第 3 家 第 3 家 第 3 家 ... ... [不能偷] / \ / \ | 偷(+3) 跳过 偷(+3) 跳过 ... ... ... ... ... 最终比较所有路径的总金额,取最大的 但这样穷举太慢了(指数级),所以用 DP 来优化 ``` --- ## 手动模拟 [2, 7, 9, 3, 1](这是理解的关键) ``` nums = [2, 7, 9, 3, 1] 初始化: dp[0] = nums[0] = 2(只有第 0 家,偷它) dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7(两家选一家,选 7) i: 0 1 2 3 4 nums: 2 7 9 3 1 dp: 2 7 _ _ _ 处理 i=2 (nums[2]=9): 偷第 2 家:dp[0] + nums[2] = 2 + 9 = 11 含义:偷第 0 家和第 2 家,收入 2 + 9 = 11 不偷第 2 家:dp[1] = 7 含义:只偷第 1 家,收入 7 dp[2] = max(11, 7) = 11 → 偷第 2 家更划算 i: 0 1 2 3 4 nums: 2 7 9 3 1 dp: 2 7 11 _ _ 处理 i=3 (nums[3]=3): 偷第 3 家:dp[1] + nums[3] = 7 + 3 = 10 含义:偷第 1 家和第 3 家,收入 7 + 3 = 10 不偷第 3 家:dp[2] = 11 含义:保持之前的最优方案(偷第 0、2 家),收入 11 dp[3] = max(10, 11) = 11 → 不偷第 3 家更划算 i: 0 1 2 3 4 nums: 2 7 9 3 1 dp: 2 7 11 11 _ 处理 i=4 (nums[4]=1): 偷第 4 家:dp[2] + nums[4] = 11 + 1 = 12 含义:偷第 0、2、4 家,收入 2 + 9 + 1 = 12 不偷第 4 家:dp[3] = 11 含义:保持之前的最优方案,收入 11 dp[4] = max(12, 11) = 12 → 偷第 4 家更划算 i: 0 1 2 3 4 nums: 2 7 9 3 1 dp: 2 7 11 11 12 答案 = dp[4] = 12(偷第 0、2、4 家:2 + 9 + 1 = 12)✓ ``` --- ## 代码 ### 写法 1:DP 数组 ```java public int rob(int[] nums) { if (nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[nums.length - 1]; } ``` 时间 O(n),空间 O(n)。 ### 写法 2:空间优化 ``` 为什么能优化? dp[i] 只依赖 dp[i-1] 和 dp[i-2] 和爬楼梯一样,只需要两个变量 ``` ```java public int rob(int[] nums) { if (nums.length == 1) return nums[0]; int prev2 = 0, prev1 = 0; for (int num : nums) { int curr = Math.max(prev1, prev2 + num); prev2 = prev1; prev1 = curr; } return prev1; } ``` 时间 O(n),空间 O(1)。 ### 空间优化的手动模拟 ``` nums = [2, 7, 9, 3, 1] 初始:prev2 = 0, prev1 = 0 处理 num=2: curr = max(0, 0+2) = 2 → prev2=0, prev1=2 处理 num=7: curr = max(2, 0+7) = 7 → prev2=2, prev1=7 处理 num=9: curr = max(7, 2+9) = 11 → prev2=7, prev1=11 处理 num=3: curr = max(11, 7+3) = 11 → prev2=11, prev1=11 处理 num=1: curr = max(11, 11+1) = 12 → prev2=11, prev1=12 返回 prev1 = 12 ✓ 注意这里初始化 prev2=0, prev1=0 和上面 dp 数组的初始化不同 但结果一样,因为循环里自然会处理前两个元素 ``` --- ## 变体:打家劫舍 II(LeetCode 213)— 环形 ### 题目 房子围成一个圈,首尾相邻。不能同时偷第一家和最后一家。 ``` 输入:[2, 3, 2] 输出:3(偷第 1 家,不能同时偷第 0 家和第 2 家因为它们相邻) ``` ### 先搞清楚:环形和线性有什么区别 ``` 线性:[2, 7, 9, 3, 1] 第 0 家和第 4 家不相邻,可以同时偷 环形:[2, 7, 9, 3, 1](首尾相连) 第 0 家和第 4 家相邻了!不能同时偷 多了一个约束:nums[0] 和 nums[n-1] 不能同时偷 ``` ### 核心思路:拆成两个线性问题 ``` 既然第一家和最后一家不能同时偷,那就分两种情况: 情况 1:不偷最后一家 → 在 nums[0..n-2] 上做线性打家劫舍 情况 2:不偷第一家 → 在 nums[1..n-1] 上做线性打家劫舍 取两种情况的最大值 为什么这样是对的? 最优解要么包含第一家,要么不包含第一家: - 包含第一家 → 一定不包含最后一家 → 被情况 1 覆盖 - 不包含第一家 → 被情况 2 覆盖 两种情况覆盖了所有可能,取最大值就是答案 ``` ### 注意:容易困惑的地方 ``` Q:情况 1 说"不偷最后一家",但 dp 的结果可能也没偷第一家啊? A:没关系!"不偷最后一家"只是限制了范围是 [0..n-2], 在这个范围内,dp 会自动决定偷不偷第一家。 我们只是保证了"不会同时偷第一家和最后一家"。 Q:两种情况会不会有重叠? A:会有重叠(比如既不偷第一家也不偷最后一家的方案两边都算了), 但我们取的是 max,重叠不影响正确性。 ``` ### 手动模拟 [2, 7, 9, 3, 1](环形) ``` 情况 1:不偷最后一家,范围 [2, 7, 9, 3](下标 0~3) prev2=0, prev1=0 num=2: curr = max(0, 0+2) = 2 → prev2=0, prev1=2 num=7: curr = max(2, 0+7) = 7 → prev2=2, prev1=7 num=9: curr = max(7, 2+9) = 11 → prev2=7, prev1=11 num=3: curr = max(11, 7+3) = 11 → prev2=11, prev1=11 结果 = 11(偷第 0、2 家:2+9=11) 情况 2:不偷第一家,范围 [7, 9, 3, 1](下标 1~4) prev2=0, prev1=0 num=7: curr = max(0, 0+7) = 7 → prev2=0, prev1=7 num=9: curr = max(7, 0+9) = 9 → prev2=7, prev1=9 num=3: curr = max(9, 7+3) = 10 → prev2=9, prev1=10 num=1: curr = max(10, 9+1) = 10 → prev2=10, prev1=10 结果 = 10(偷第 1、3 家:7+3=10) 答案 = max(11, 10) = 11 验证:偷第 0 家(2)和第 2 家(9),收入 11 第 0 家和第 2 家不相邻 ✓ 第 0 家和第 4 家(环形相邻)没有同时偷 ✓ ``` ### 再来一个例子 [1, 2, 3, 1](环形) ``` 情况 1:范围 [1, 2, 3](下标 0~2) prev2=0, prev1=0 num=1: curr = max(0, 0+1) = 1 → prev2=0, prev1=1 num=2: curr = max(1, 0+2) = 2 → prev2=1, prev1=2 num=3: curr = max(2, 1+3) = 4 → prev2=2, prev1=4 结果 = 4(偷第 0、2 家:1+3=4) 情况 2:范围 [2, 3, 1](下标 1~3) prev2=0, prev1=0 num=2: curr = max(0, 0+2) = 2 → prev2=0, prev1=2 num=3: curr = max(2, 0+3) = 3 → prev2=2, prev1=3 num=1: curr = max(3, 2+1) = 3 → prev2=3, prev1=3 结果 = 3(偷第 1 家:3,或偷第 1、3 家:2+1=3) 答案 = max(4, 3) = 4(偷第 0、2 家:1+3=4)✓ ``` ### 代码 ```java public int rob(int[] nums) { if (nums.length == 1) return nums[0]; if (nums.length == 2) return Math.max(nums[0], nums[1]); // 两种情况取最大值 return Math.max( robRange(nums, 0, nums.length - 2), // 不偷最后一家 robRange(nums, 1, nums.length - 1) // 不偷第一家 ); } // 线性打家劫舍,范围 [start, end] private int robRange(int[] nums, int start, int end) { int prev2 = 0, prev1 = 0; for (int i = start; i <= end; i++) { int curr = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; } ``` 时间 O(n),空间 O(1)。 --- ## 注意:容易困惑的地方 ``` Q:dp[i] 到底是"偷到第 i 家的最大金额"还是"一定偷第 i 家的最大金额"? A:是"考虑完前 i 家后的最大金额",不一定偷第 i 家。 dp[i] = max(dp[i-1], dp[i-2]+nums[i]) 如果 dp[i] = dp[i-1],说明不偷第 i 家更好。 Q:为什么不能用贪心(每次偷金额最大的那家)? A:因为偷了一家会影响相邻的家能不能偷,局部最优不等于全局最优。 比如 [1, 100, 1, 1, 100],贪心先偷第一个 100, 但最优是偷两个 100(第 1 家和第 4 家)= 200。 Q:如果 nums 只有 1 个元素或 2 个元素怎么办? A:1 个元素:直接返回 nums[0] 2 个元素:返回 max(nums[0], nums[1]) 这就是边界情况,代码里要特判。 ``` --- ## 两道题对比 ``` 题目 约束 转化方式 打家劫舍 I 线性,不偷相邻 直接 DP 打家劫舍 II 环形,不偷相邻 拆成两个线性问题(去掉首 or 去掉尾) ``` ## 一句话总结 每家偷或不偷:`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`。环形就拆成两个线性问题——不偷第一家或不偷最后一家,取最大值。 --- 上一篇:[02 - 爬楼梯](./02-climbing-stairs.md) | 下一篇:[04 - 最长递增子序列](./04-lis.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入