[特殊字符] 第73课:打家劫舍

想系统提升编程能力、查看更完整的学习路线欢迎访问 AI Compasshttps://github.com/tingaicompass/AI-Compass仓库持续更新刷题题解、Python 基础和 AI 实战内容适合想高效进阶的你。 第73课:打家劫舍模块:动态规划 |难度:Medium ⭐⭐⭐LeetCode 链接:https://leetcode.cn/problems/house-robber/前置知识:第71课《爬楼梯》预计学习时间:25分钟 题目描述你是一个专业的小偷,计划偷窃沿街的房屋。每间房都藏有一定的现金,但有个安全系统会检测:如果两间相邻的房屋在同一晚上被小偷闯入,系统就会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报系统的前提下,一夜之内能够偷窃到的最高金额。示例:输入:nums [1,2,3,1] 输出:4 解释:偷窃1号房(金额1)和3号房(金额3),总金额 1 3 4约束条件:1 nums.length 1000 nums[i] 400不能偷相邻的房屋 边界用例(面试必考)用例类型输入期望输出考察点最小输入nums [1]1只有一间房两间房nums [2,1]2选较大的交替最优nums [2,7,9,3,1]12选02429112大规模n100,全为400需要DP避免超时性能边界全0nums [0,0,0]0特殊值处理 思路引导生活化比喻想象你在玩一个石头跳跃游戏,站在每块石头上都能捡到金币,但你不能连续踩两块相邻的石头,否则就会掉下去。笨办法:用回溯法枚举所有可能的偷窃组合(偷/不偷第1间,偷/不偷第2间…),时间复杂度 O(2n),100间房就是2100种可能!聪明办法:站在每间房门口,只需要问自己:“如果我已经知道’偷到前一间的最大值’和’偷到前两间的最大值’,那当前这间房怎么选收益最大?” 这就是动态规划的核心思想——用已知答案推导新答案。关键洞察到第i间房时,有两个选择:偷它或不偷它。偷它就不能偷i-1,不偷就沿用i-1的最大值。取两者最大即可。 解题思维链这一节模拟你在面试中从零开始思考的过程。Step 1:理解题目 → 锁定输入输出输入:整数数组 nums,表示每间房的金额输出:最大偷窃金额(整数)限制:不能偷相邻的房屋,即 nums[i] 和 nums[i1] 不能同时偷Step 2:先想笨办法(暴力法)用递归枚举每间房偷或不偷两种选择,求所有合法方案的最大值:defrob(i):ifi0:return0returnmax(rob(i-1),rob(i-2)nums[i])时间复杂度:O(2^n) — 每层分裂成两个分支,指数爆炸瓶颈在哪:大量重复计算,比如 rob(5) 会被 rob(6) 和 rob(7) 重复计算多次Step 3:瓶颈分析 → 优化方向暴力递归中,rob(i) 会被重复计算无数次,但它的结果其实只依赖于 nums[i]、rob(i-1)、rob(i-2)。核心问题:重复计算子问题优化思路:把计算过的结果记录下来,下次遇到直接查表 →记忆化搜索 or 动态规划Step 4:选择武器选用:动态规划(DP)理由:问题有最优子结构(当前最优解依赖子问题最优解)和重叠子问题(大量重复计算),是DP的典型特征模式识别提示:当题目出现最大值/最小值且每一步有选/不选的决策时,优先考虑DP五步法 解法一:自顶向下记忆化递归(直觉法)思路在暴力递归的基础上,用一个字典(或数组)记录已经计算过的 rob(i),避免重复计算。图解过程输入:nums [2, 7, 9, 3, 1] 递归树(带记忆): rob(4) / \ rob(3) rob(2)1 / \ / \ rob(2) rob(1)3 rob(1) rob(0)9 / \ / \ / \ / \ ... ... ... ... ... ... ... ... (多次遇到 rob(2)、rob(1) 时直接查表,不再重复计算) 最终:rob(4) max(rob(3), rob(2)1) max(12, 11) 12Python代码fromtypingimportListdefrob_memo(nums:List[int])-int: 解法一:自顶向下记忆化递归 思路:用字典缓存已计算的子问题结果 memo{}# 缓存defdp(i:int)-int:# 递归终止条件ifi0:return0ifiinmemo:returnmemo[i]# 查表# 状态转移:当前房偷或不偷memo[i]max(dp(i-1),dp(i-2)nums[i])returnmemo[i]returndp(len(nums)-1)# ✅ 测试print(rob_memo([1,2,3,1]))# 期望输出:4print(rob_memo([2,7,9,3,1]))# 期望输出:12print(rob_memo([2,1,1,2]))# 期望输出:4复杂度分析时间复杂度(n) — 每个子问题只计算一次,共 n 个子问题具体地说:如果 n100,大约需要 100 次计算(对比暴力的 2^100 次!)空间复杂度(n) — memo字典存储 n 个结果 递归栈深度 O(n)优缺点✅ 代码自然,和递归思路一致,容易理解❌ 有递归栈开销,可能栈溢出(虽然题目n100不会)⚡ 解法二:自底向上动态规划(标准DP)优化思路既然已经知道递归的方向是从 i0 推到 in-1,那不如反过来,从小到大直接用循环填表,省去递归开销。关键想法:dp[i] 偷到第i间房时的最大金额,由 dp[i-1] 和 dp[i-2] 推导而来图解过程输入:nums [2, 7, 9, 3, 1] 初始化: dp[0] 2 (只有第0间,必须偷) dp[1] max(2, 7) 7 (偷第0或第1间,选大的) 迭代计算: i2: dp[2] max(dp[1], dp[0]9) max(7, 29) 11 └─ 不偷2 └─ 偷2(要跳过1) i3: dp[3] max(dp[2], dp[1]3) max(11, 73) 11 i4: dp[4] max(dp[3], dp[2]1) max(11, 111) 12 最终答案:dp[4] 12状态转移图示:房屋: [ 2, 7, 9, 3, 1] dp值: [ 2, 7, 11, 11, 12] └──────┘ └──────┘ 选dp[i-1] 选dp[i-2]nums[i]Python代码defrob_dp(nums:List[int])-int: 解法二:自底向上动态规划 思路:用数组dp[i]记录到第i间房的最大金额 nlen(nums)ifn0:return0ifn1:returnnums[0]# 定义状态数组dp[0]*n dp[0]nums[0]# 只有一间房,偷它dp[1]max(nums[0],nums[1])# 两间房,偷大的# 状态转移foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])# 不偷i 偷i(跳过i-1)returndp[n-1]# ✅ 测试print(rob_dp([1,2,3,1]))# 期望输出:4print(rob_dp([2,7,9,3,1]))# 期望输出:12print(rob_dp([2,1,1,2]))# 期望输出:4复杂度分析时间复杂度(n) — 一次遍历空间复杂度(n) — dp数组 解法三:空间优化DP(最优解)优化思路观察状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i]),发现当前状态只依赖前两个状态,不需要保存整个数组,只需要两个变量!关键想法:用滚动变量 prev2、prev1 代替 dp[i-2]、dp[i-1]图解过程输入:nums [2, 7, 9, 3, 1] 初始:prev20, prev10 i0: curr max(0, 02) 2 更新:prev20, prev12 i1: curr max(2, 07) 7 更新:prev22, prev17 i2: curr max(7, 29) 11 更新:prev27, prev111 i3: curr max(11, 73) 11 更新:prev211, prev111 i4: curr max(11, 111) 12 更新:prev211, prev112 答案:12Python代码defrob_optimized(nums:List[int])-int: 解法三:空间优化DP(最优解) 思路:用两个变量代替数组,空间降到O(1) prev20# dp[i-2]prev10# dp[i-1]fornuminnums:currmax(prev1,prev2num)# 状态转移prev2prev1# 更新前两项prev1currreturnprev1# ✅ 测试print(rob_optimized([1,2,3,1]))# 期望输出:4print(rob_optimized([2,7,9,3,1]))# 期望输出:12print(rob_optimized([2,1,1,2]))# 期望输出:4复杂度分析时间复杂度(n) — 一次遍历具体地说:n100 时,只需100次操作空间复杂度(1) — 只用3个变量(prev2、prev1、curr) Pythonic 写法利用 Python 的多重赋值,代码可以更简洁:defrob_pythonic(nums:List[int])-int:Pythonic写法:利用元组解包prev2,prev10,0fornuminnums:prev2,prev1prev1,max(prev1,prev2num)returnprev1⚠️面试建议:先写清晰的解法二展示DP思路,再提解法三展示优化能力,最后补充Pythonic写法展示语言功底。面试官更看重你的思考过程,而非代码行数。 解法对比维度解法一:记忆化递归解法二:标准DP 解法三:空间优化DP(最优)时间复杂度O(n)O(n)O(n)← 时间最优空间复杂度O(n)O(n)O(1)← 空间最优代码难度中等简单简单面试推荐⭐⭐⭐⭐⭐⭐⭐⭐← 首选适用场景理解递归思路标准DP模板学习面试首选,时空双优为什么解法三是最优解:时间 O(n) 已经是理论最优(至少要看一遍所有房屋)空间优化到 O(1),只需常数级额外空间代码简洁,面试中容易写对且不易出错面试建议:先用30秒口述暴力递归思路(O(2^n)),表明你理解问题本质立即提出用DP优化,写出解法二(标准DP数组)重点讲解空间优化:“观察到只需要前两项,用滚动变量优化到O(1)”强调为什么这是最优:时间已达下限,空间进一步优化手动测试边界用例(单间房、两间房),展示严谨性 面试现场模拟面试中的完整对话流程,帮你练习边想边说。面试官:请你解决一下这道打家劫舍问题。你:(审题30秒)好的,这道题要求在不偷相邻房屋的前提下,求能偷到的最大金额。让我先想一下…我的第一个想法是用递归:对每间房选择偷或不偷,递归求最大值。但这样时间复杂度是 O(2^n),会超时。观察到这是一个典型的动态规划问题:到第i间房时的最大金额,只依赖于前面的结果。我可以用DP优化到 O(n)。核心状态转移是:dp[i] max(dp[i-1], dp[i-2] nums[i])。面试官:很好,请写一下代码。你:(边写边说)我先定义dp数组,dp[i]表示到第i间房的最大金额。初始化dp[0]nums[0],dp[1]max(nums[0], nums[1])。然后从i2开始遍历,每次取不偷当前和偷当前的最大值…(写完解法二代码)面试官:空间能不能优化?你:可以!观察到状态转移只用到 dp[i-1] 和 dp[i-2],不需要保存整个数组。我可以用两个变量 prev1、prev2 滚动更新,空间优化到 O(1)。(写出解法三代码)面试官:测试一下?你:用示例 [2,7,9,3,1] 走一遍:i0: currmax(0, 02)2i1: currmax(2, 07)7i2: currmax(7, 29)11i3: currmax(11, 73)11i4: currmax(11, 111)12 ✓再测边界 [1]:直接返回1 ✓高频追问追问应答策略“如果房屋是环形的(首尾相邻)怎么办?”这就是LeetCode 213。需要拆成两个子问题:1)偷第一间,不偷最后一间 2)不偷第一间,偷最后一间,取两者最大值“如果每间房有不同的偷窃成本呢?”状态转移改为dp[i] max(dp[i-1], dp[i-2] value[i] - cost[i]),本质不变“能用贪心吗?”不能。反例:[2,1,1,2],贪心选224 ✓,但 [1,100,1,1,100] 贪心会选100100200,最优是11001100202,需要DP“这个思路能解决什么其他题?”股票买卖(LC 121)、删除并获得点数(LC 740)、粉刷房子(LC 256),都是选/不选DP模式 知识点总结Python技巧卡片 # 技巧1:多重赋值优雅更新 — 一行实现滚动变量prev2,prev1prev1,max(prev1,prev2num)# 等价于:# temp max(prev1, prev2 num)# prev2 prev1# prev1 temp# 技巧2:边界处理 — 提前返回简化代码ifn1:returnnums[0]ifn2:returnmax(nums[0],nums[1])# 避免后续判断,代码更清晰# 技巧3:functools.lru_cache装饰器 — 自动记忆化fromfunctoolsimportlru_cachelru_cache(maxsizeNone)defrob(i):ifi0:return0returnmax(rob(i-1),rob(i-2)nums[i]) 底层原理(选读)为什么DP能优化指数复杂度?暴力递归的问题在于重复计算。以 rob(5) 为例:rob(6) 会算一次 rob(5)rob(7) 也会算一次 rob(5)rob(8)、rob(9)…都会重复算DP的本质是记录已知结果,避免重复计算。通过空间换时间,把指数级的重复计算减少到线性。DP vs 贪心的区别?贪心:每一步都选局部最优,不需要回头看(如跳跃游戏:每次跳最远)DP:当前决策依赖于之前的多个状态,需要记录历史(如打家劫舍:偷不偷当前房,要看前两间的结果)判断方法:如果当前最优能直接推出全局最优→贪心;如果需要比较多个历史状态→DP算法模式卡片 模式名称:线性DP — 选/不选决策适用条件:每一步有选择A或选择B两种互斥决策当前最优解依赖于前面有限的几个状态(通常是前1-2个)求最优值(最大/最小)识别关键词:“不能相邻”、“隔一个”、“选或不选”、“最大收益”DP五步法:定义状态: dp[i] 到第i个元素时的最优值状态转移: dp[i] max/min(选它, 不选它)初始化: dp[0]、dp[1] 直接赋值遍历顺序: 从小到大(i从2到n-1)返回值: dp[n-1] 或 max(dp)模板代码:deflinear_dp_select(nums):nlen(nums)ifn0:return0ifn1:returnnums[0]dp[0]*n dp[0]nums[0]dp[1]max(nums[0],nums[1])foriinrange(2,n):dp[i]max(dp[i-1],dp[i-2]nums[i])# 不选i 选i(跳过i-1)returndp[n-1]易错点 ⚠️边界初始化错误:# ❌ 错误:忘记处理 n1 的情况dp[1]max(nums[0],nums[1])# 数组越界!# ✓ 正确:先判断边界ifn1:returnnums[0]状态转移理解错误:# ❌ 错误:以为只能隔一个房偷dp[i]dp[i-2]nums[i]# 错!可能不偷i更优# ✓ 正确:选和不选取最大值dp[i]max(dp[i-1],dp[i-2]nums[i])空间优化时变量更新顺序错误:# ❌ 错误:先更新prev1,再更新prev2prev1max(prev1,prev2num)prev2prev1# 错!prev2被错误覆盖# ✓ 正确:同时更新或用临时变量prev2,prev1prev1,max(prev1,prev2num)️ 工程实战(选读)这个算法思想在真实项目中的应用,让你知道学了有什么用。场景1:任务调度系统— 服务器资源分配时,某些任务不能同时运行(如都需要独占GPU),求最大吞吐量场景2:投资组合优化— 某些股票有关联性(如同行业),不能同时持有,求最大收益组合场景3:广告位竞价— 相邻广告位不能给同一广告主(避免霸屏),求收益最大的广告组合️ 举一反三完成本课后,试试这些同类题目来巩固知识:题目难度相关知识点提示LeetCode 213. 打家劫舍IIMedium环形DP拆成两个子问题:含首不含尾 vs 含尾不含首LeetCode 337. 打家劫舍IIIMedium树形DP在二叉树上做DP,每个节点记录偷/不偷两种状态LeetCode 740. 删除并获得点数Medium线性DP转化为打家劫舍:值相同的数字看作一间房LeetCode 256. 粉刷房子Medium选择DP每间房选颜色,相邻不同色,求最小成本 课后小测试试这道变体题,不要看答案,自己先想5分钟!题目:如果每间房有一个偷窃难度数组difficulty[],偷第i间房需要消耗difficulty[i]点体力,你总共有energy点体力。在不触发警报的前提下,求最大偷窃金额。 提示(实在想不出来再点开)加一维状态:dp[i][j] 偷到第i间房,消耗j点体力时的最大金额。状态转移时要判断体力是否足够。✅ 参考答案defrob_with_energy(nums:List[int],difficulty:List[int],energy:int)-int: 二维DP:dp[i][j] 偷到第i间房,用了j点体力时的最大金额 nlen(nums)# dp[i][j] 表示前i间房,消耗j体力的最大金额dp[[-1]*(energy1)for_inrange(n1)]dp[0][0]0# 0间房,0体力,0金额foriinrange(1,n1):forjinrange(energy1):# 不偷第i间房(下标i-1)dp[i][j]dp[i-1][j]# 偷第i间房(需要跳过i-1,体力够)ifjdifficulty[i-1]andi2:ifdp[i-2][j-difficulty[i-1]]!-1:dp[i][j]max(dp[i][j],dp[i-2][j-difficulty[i-1]]nums[i-1])elifi1andjdifficulty[0]:dp[i][j]nums[0]returnmax(dp[n])# 返回n间房,任意体力下的最大值核心思路:在原状态 dp[i] 基础上增加一维体力消耗,变成二维DP。时间复杂度 O(n * energy),空间可优化到 O(energy)。如果这篇内容对你有帮助推荐收藏 AI Compasshttps://github.com/tingaicompass/AI-Compass更多系统化题解、编程基础和 AI 学习资料都在这里后续复习和拓展会更省时间。