LeetCode 198. 打家劫舍：动态规划入门经典题详解

作为动态规划领域最经典的入门题目之一LeetCode 198. 打家劫舍不仅考察对「状态定义」和「递推逻辑」的理解更能帮我们建立解决“选或不选”类问题的核心思维。今天就带大家一步步拆解这道题从题目分析到代码实现吃透每一个细节新手也能轻松掌握。一、题目解读读懂约束明确目标题目核心场景很简单沿街有若干房屋每间房有一定现金相邻房屋不能同时偷窃否则触发警报给定房屋现金数组nums求一夜能偷窃到的最高金额。关键约束拆解约束相邻房屋互斥选了第i间就不能选第i-1间不选第i间可选择第i-1间或不选。目标求“最大金额”属于「最优化问题」——这类问题往往适合用动态规划求解通过记录中间状态避免重复计算。边界情况数组为空无房屋、数组长度为1只有一间房需单独处理。二、动态规划思路从“状态”到“递推”动态规划的核心是「定义状态」和「找到递推公式」我们一步步推导1. 定义DP状态我们定义dp[i]表示偷窃前i1间房屋即下标0到i的房屋能获得的最高金额。为什么这么定义因为每一步的决策偷或不偷第i间房都依赖于前一步的结果用dp[i]记录前i1间的最优解能自然衔接后续的递推。2. 推导递推公式对于第i间房屋我们有两种选择偷或者不偷。选择1偷第i间房。那么第i-1间房不能偷此时最高金额 前i-1间房的最优解dp[i-2] 第i间房的现金nums[i]。选择2不偷第i间房。那么最高金额 前i间房的最优解dp[i-1]相当于直接继承前i间的最好结果。我们要的是“最高金额”所以取两种选择的最大值递推公式如下dp[i]max(dp[i−2]nums[i],dp[i−1])dp[i] max(dp[i-2] nums[i], dp[i-1])dp[i]max(dp[i−2]nums[i],dp[i−1])3. 初始化边界状态递推公式需要dp[i-2]和dp[i-1]所以我们需要先初始化前两个状态当只有1间房i0dp[0] nums[0]只能偷这一间。当有2间房i1dp[1] max(nums[0], nums[1])选现金多的那一间偷。4. 遍历顺序从i2开始依次遍历到数组末尾i size-1因为每一个dp[i]都依赖于前面的dp[i-1]和dp[i-2]顺序遍历才能保证我们用到的状态都是已经计算好的。三、代码逐行解析把思路落地给定的代码已经完美实现了上述思路我们逐行拆解看懂每一步的作用functionrob(nums:number[]):number{// 边界情况1没有房子返回0if(nums.length0)return0;constsizenums.length;// 边界情况2只有一间房返回该房的现金if(size1)returnnums[0];// 初始化dp数组存储前i1间房的最高偷窃金额constdp:number[]newArray(size);dp[0]nums[0];// 前1间房下标0的最优解dp[1]Math.max(nums[0],nums[1]);// 前2间房的最优解// 递推从第3间房i2开始直到最后一间房for(leti2;isize;i){dp[i]Math.max(dp[i-2]nums[i],dp[i-1]);}// 返回最后一间房对应的最优解前size间房的最高金额returndp[size-1];};关键代码说明边界处理先判断数组为空和长度为1的情况避免后续数组越界也符合实际场景。dp数组初始化长度和nums一致确保每一间房都有对应的状态记录。循环递推i从2开始逐一计算每一间房的最优解最终dp[size-1]就是所有房屋的最高偷窃金额。四、测试案例验证思路正确性我们用两个常见测试案例看看代码是否能正常运行案例1nums [1,2,3,1]推导过程dp[0] 1dp[1] max(1,2) 2dp[2] max(dp[0]3, dp[1]) max(13, 2) 4dp[3] max(dp[1]1, dp[2]) max(21, 4) 4返回结果4正确偷窃第1间和第3间134。案例2nums [2,7,9,3,1]推导过程dp[0] 2dp[1] max(2,7) 7dp[2] max(29,7) 11dp[3] max(73,11) 11dp[4] max(111,11) 12返回结果12正确偷窃第1间、第3间、第5间29112。五、优化方向空间复杂度优化上述代码的空间复杂度是O(n)用到了长度为n的dp数组但我们观察递推公式发现dp[i]只依赖于dp[i-1]和dp[i-2]不需要存储整个数组。可以用两个变量替代dp数组将空间复杂度优化到O(1)优化后代码如下供参考functionrob(nums:number[]):number{if(nums.length0)return0;if(nums.length1)returnnums[0];letprevPrevnums[0];// 对应dp[i-2]letprevMath.max(nums[0],nums[1]);// 对应dp[i-1]for(leti2;inums.length;i){constcurrentMath.max(prevPrevnums[i],prev);prevPrevprev;prevcurrent;}returnprev;};优化思路用prevPrev记录dp[i-2]prev记录dp[i-1]每次循环更新这两个变量避免存储整个dp数组效率更高。六、总结掌握动态规划的核心思维打家劫舍这道题的核心是「用状态记录中间最优解用递推公式衔接前后决策」。其实很多动态规划题都是这个思路明确问题的约束和目标相邻不偷求最大金额定义合适的状态dp[i]代表前i1间房的最优解推导递推公式偷或不偷的两种选择取最大值初始化边界顺序遍历计算可选优化空间复杂度去掉不必要的存储。这道题作为动态规划的入门题难度适中但能帮我们建立“最优子结构”和“无后效性”的思维——后续遇到类似的“选或不选”“相邻约束”问题如打家劫舍II、III都能沿用这个思路。