LeetCode 198. 打家劫舍：动态规划入门经典题详解-平芜编程栈

作为动态规划领域最经典的入门题目之一，LeetCode 198. 打家劫舍不仅考察对「状态定义」和「递推逻辑」的理解，更能帮我们建立解决“选或不选”类问题的核心思维。今天就带大家一步步拆解这道题，从题目分析到代码实现，吃透每一个细节，新手也能轻松掌握。

一、题目解读：读懂约束，明确目标

题目核心场景很简单：沿街有若干房屋，每间房有一定现金，相邻房屋不能同时偷窃（否则触发警报），给定房屋现金数组nums，求一夜能偷窃到的最高金额。

关键约束拆解：

约束：相邻房屋互斥，选了第i间，就不能选第i-1间；不选第i间，可选择第i-1间（或不选）。
目标：求“最大金额”，属于「最优化问题」——这类问题往往适合用动态规划求解，通过记录中间状态，避免重复计算。
边界情况：数组为空（无房屋）、数组长度为1（只有一间房），需单独处理。

二、动态规划思路：从“状态”到“递推”

动态规划的核心是「定义状态」和「找到递推公式」，我们一步步推导：

1. 定义DP状态

我们定义dp[i]表示：偷窃前i+1间房屋（即下标0到i的房屋），能获得的最高金额。

为什么这么定义？因为每一步的决策（偷或不偷第i间房），都依赖于前一步的结果，用dp[i]记录前i+1间的最优解，能自然衔接后续的递推。

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间房（i=0）：dp[0] = nums[0]（只能偷这一间）。
当有2间房（i=1）：dp[1] = max(nums[0], nums[1])（选现金多的那一间偷）。

4. 遍历顺序

从i=2开始，依次遍历到数组末尾（i = size-1），因为每一个dp[i]都依赖于前面的dp[i-1]和dp[i-2]，顺序遍历才能保证我们用到的状态都是已经计算好的。

三、代码逐行解析：把思路落地

给定的代码已经完美实现了上述思路，我们逐行拆解，看懂每一步的作用：

functionrob(nums:number[]):number{// 边界情况1：没有房子，返回0if(nums.length===0)return0;constsize=nums.length;// 边界情况2：只有一间房，返回该房的现金if(size===1)returnnums[0];// 初始化dp数组，存储前i+1间房的最高偷窃金额constdp:number[]=newArray(size);dp[0]=nums[0];// 前1间房（下标0）的最优解dp[1]=Math.max(nums[0],nums[1]);// 前2间房的最优解// 递推：从第3间房（i=2）开始，直到最后一间房for(leti=2;i<size;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]就是所有房屋的最高偷窃金额。

四、测试案例：验证思路正确性

我们用两个常见测试案例，看看代码是否能正常运行：

案例1：nums = [1,2,3,1]

推导过程：

dp[0] = 1
dp[1] = max(1,2) = 2
dp[2] = max(dp[0]+3, dp[1]) = max(1+3, 2) = 4
dp[3] = max(dp[1]+1, dp[2]) = max(2+1, 4) = 4

返回结果：4（正确，偷窃第1间和第3间，1+3=4）。

案例2：nums = [2,7,9,3,1]

推导过程：

dp[0] = 2
dp[1] = max(2,7) = 7
dp[2] = max(2+9,7) = 11
dp[3] = max(7+3,11) = 11
dp[4] = max(11+1,11) = 12

返回结果：12（正确，偷窃第1间、第3间、第5间，2+9+1=12）。

五、优化方向：空间复杂度优化

上述代码的空间复杂度是O(n)（用到了长度为n的dp数组），但我们观察递推公式发现：dp[i]只依赖于dp[i-1]和dp[i-2]，不需要存储整个数组。

可以用两个变量替代dp数组，将空间复杂度优化到O(1)，优化后代码如下（供参考）：

functionrob(nums:number[]):number{if(nums.length===0)return0;if(nums.length===1)returnnums[0];letprevPrev=nums[0];// 对应dp[i-2]letprev=Math.max(nums[0],nums[1]);// 对应dp[i-1]for(leti=2;i<nums.length;i++){constcurrent=Math.max(prevPrev+nums[i],prev);prevPrev=prev;prev=current;}returnprev;};