【每日算法】LeetCode 198. 打家劫舍(动态规划)

对前端开发者而言，学习算法绝非为了"炫技"。它是你从"页面构建者"迈向"复杂系统设计者"的关键阶梯。它将你的编码能力从"实现功能"提升到"设计优雅、高效解决方案"的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 198. 打家劫舍

1. 题目描述

打家劫舍是一个经典的动态规划问题。题目描述如下：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素是：相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4。

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12。

2. 问题分析

2.1 问题本质

这个问题本质上是一个最优化问题，需要在约束条件下（不能偷相邻房屋）找到最大收益的方案。这类问题在前端开发中其实很常见：

• 资源加载优化：某些资源不能同时加载（冲突），如何安排加载顺序最大化性能收益
• 任务调度：某些任务不能同时执行，如何安排执行顺序最大化完成价值
• 缓存策略：某些缓存不能同时存在，如何选择缓存内容最大化命中率

2.2 关键特征

1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：在递归求解过程中，子问题会被重复计算多次
3. 无后效性：当前状态只与前面有限个状态有关

3. 解题思路

3.1 暴力递归法（理解问题本质）

最直观的想法：对于每个房屋，我们有两种选择：

• 偷这个房屋，然后跳过下一个房屋
• 不偷这个房屋，考虑下一个房屋

/** * 暴力递归解法 - 用于理解问题（会超时） * 时间复杂度：O(2^n) - 指数级，不可接受 * 空间复杂度：O(n) - 递归调用栈深度 */functionrobRecursive(nums){// 辅助递归函数functionhelper(i){// 边界条件：没有房屋可偷if(i>=nums.length)return0;// 两种选择：// 1. 偷当前房屋，然后考虑 i+2 之后的房屋conststealCurrent=nums[i]+helper(i+2);// 2. 不偷当前房屋，考虑 i+1 之后的房屋constskipCurrent=helper(i+1);// 返回两种选择中的最大值returnMath.max(stealCurrent,skipCurrent);}returnhelper(0);}

3.2 动态规划解法（最优解）

动态规划是解决这类问题的标准方法。我们可以用两种方式实现：

3.2.1 自顶向下 - 记忆化搜索

3.2.2 自底向上 - 迭代递推

最优解分析：

• 时间复杂度：O(n) - 只需遍历一次数组
• 空间复杂度：O(1) - 只需常数空间存储前两个状态
• 这是最优解法，无法在时间复杂度上进一步优化

4. 代码实现

4.1 方法一：动态规划（标准数组版）

/** * 动态规划 - 标准数组版 * 时间复杂度：O(n) * 空间复杂度：O(n) * * 思路分析： * 1. 定义状态：dp[i] 表示偷到第 i 个房屋（不一定偷第 i 个）时的最大收益 * 2. 状态转移：对于每个房屋，有两种选择： * - 偷：dp[i] = dp[i-2] + nums[i]（不能偷相邻的，所以看 i-2） * - 不偷：dp[i] = dp[i-1]（直接继承前一个状态） * 取两者较大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) * 3. 初始状态：dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) * 4. 返回结果：dp[n-1] */functionrobDP(nums){// 边界情况处理if(!nums||nums.length===0)return0;if(nums.length===1)returnnums[0];if(nums.length===2)returnMath.max(nums[0],nums[1]);// 创建dp数组constn=nums.length;constdp=newArray(n);// 初始化前两个状态dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);// 状态转移for(leti=2;i<n;i++){// 关键状态转移方程dp[i]=Math.max(dp[i-1],// 不偷当前房屋dp[i-2]+nums[i]// 偷当前房屋);}returndp[n-1];}

4.2 方法二：动态规划（空间优化版 - 最优解）

/** * 动态规划 - 空间优化版（最优解） * 时间复杂度：O(n) * 空间复杂度：O(1) * * 优化思路： * 观察状态转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) * 发现当前状态只依赖于前两个状态，所以不需要保存整个dp数组 * 只需要用两个变量滚动更新即可 */functionrob(nums){// 处理边界情况if(!nums||nums.length===0)return0;if(nums.length===1)returnnums[0];// 初始化前两个状态letprev2=0;// dp[i-2]letprev1=0;// dp[i-1]// 遍历所有房屋for(leti=0;i<nums.length;i++){// 计算当前状态：max(不偷当前, 偷当前)constcurrent=Math.max(prev1,prev2+nums[i]);// 滚动更新：为下一个房屋做准备// prev2 变成 prev1，prev1 变成 currentprev2=prev1;prev1=current;}// 返回最后一个房屋处理完后的最大收益returnprev1;}

4.3 方法三：动态规划（状态机思路）

/** * 动态规划 - 状态机思路 * 更符合前端状态管理思维的实现方式 * * 思路： * 定义两个状态： * - robbed：偷了当前房屋后的最大收益 * - notRobbed：没偷当前房屋的最大收益 * 每次遍历时更新这两个状态 */functionrobStateMachine(nums){if(!nums||nums.length===0)return0;// 初始化状态letrobbed=0;// 偷了当前房屋的最大收益letnotRobbed=0;// 没偷当前房屋的最大收益for(constmoneyofnums){// 保存上一轮的状态，用于计算constprevRobbed=robbed;constprevNotRobbed=notRobbed;// 状态转移：// 1. 如果这轮要偷，上一轮必须没偷：robbed = prevNotRobbed + money// 2. 如果这轮不偷，上一轮可以偷也可以不偷：notRobbed = max(prevRobbed, prevNotRobbed)robbed=prevNotRobbed+money;notRobbed=Math.max(prevRobbed,prevNotRobbed);}// 返回最终的最大值returnMath.max(robbed,notRobbed);}

4.4 前端实际应用示例

/** * 前端场景：资源加载优化问题 * 假设有多个资源需要加载，某些资源不能同时加载（会冲突） * 每个资源加载后有对应的性能收益值 * 求最大收益的加载方案 */functionoptimizeResourceLoading(resources){// resources: [{id: 'a', value: 100, conflicts: ['b']}, ...]// 简化为打家劫舍问题：将冲突关系建模为相邻关系// 假设资源按顺序排列，相邻资源不能同时加载// 将资源价值提取为数组constvalues=resources.map(r=>r.value);// 使用打家劫舍算法求解returnrob(values);}// 实际使用示例constpageResources=[{id:'script1',value:30,size:100},{id:'style1',value:25,size:50},{id:'script2',value:40,size:80},{id:'image1',value:20,size:200},{id:'script3',value:35,size:120}];console.log('最大加载收益:',optimizeResourceLoading(pageResources));

5. 各实现思路的复杂度、优缺点对比

方法	时间复杂度	空间复杂度	优点	缺点	适用场景
暴力递归	O(2ⁿ)	O(n)	思路直观，易于理解	效率极低，会超时	仅用于理解问题本质
动态规划（数组）	O(n)	O(n)	代码清晰，易于调试	空间占用较多	教学、中等规模数据
动态规划（空间优化）	O(n)	O(1)	空间最优，效率高	状态转移不够直观	生产环境、大规模数据
状态机思路	O(n)	O(1)	符合前端思维，易于理解状态变化	需要理解状态机概念	状态管理复杂的场景

6. 总结

6.1 通用解题模板

对于这类一维动态规划问题，可以总结出通用解题步骤：

/** * 一维动态规划通用框架 */functiondpTemplate(nums){// 1. 处理边界情况if(!nums||nums.length===0)return0;if(nums.length===1)returnnums[0];// 2. 定义状态（这里使用滚动数组优化）letprev2=0;// dp[i-2]letprev1=0;// dp[i-1]// 3. 状态转移for(leti=0;i<nums.length;i++){// 根据具体问题定义状态转移方程constcurrent=Math.max(prev1,prev2+nums[i]);// 4. 滚动更新状态prev2=prev1;prev1=current;}// 5. 返回结果returnprev1;}

6.2 核心思想提炼

1. 定义状态：明确 dp[i] 表示什么
2. 状态转移方程：找到 dp[i] 与前面状态的关系
3. 初始状态：确定 dp[0]、dp[1] 等初始值
4. 空间优化：观察状态依赖关系，看是否能优化空间

6.3 类似题目推荐

1. LeetCode 213. 打家劫舍 II（房屋围成一圈）

   • 解题思路：分解为两个线性问题（偷第一家或不偷第一家）

2. LeetCode 337. 打家劫舍 III（房屋是二叉树结构）

   • 解题思路：树形DP，后序遍历

3. LeetCode 740. 删除与获得点数

   • 解题思路：转化为打家劫舍问题

4. LeetCode 276. 栅栏涂色（相邻不能同色）

   • 解题思路：状态转移类似，但有k种颜色

5. LeetCode 1981. 最小化目标值与所选元素的差

   • 解题思路：类似背包问题的DP