)
对前端开发者而言，学习算法绝非为了"炫技"。它是你从"页面构建者"迈向"复杂系统设计者"的关键阶梯。它将你的编码能力从"实现功能"提升到"设计优雅、高效解决方案"的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎
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 关键特征
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：在递归求解过程中，子问题会被重复计算多次
- 无后效性：当前状态只与前面有限个状态有关
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 核心思想提炼
- 定义状态：明确 dp[i] 表示什么
- 状态转移方程：找到 dp[i] 与前面状态的关系
- 初始状态：确定 dp[0]、dp[1] 等初始值
- 空间优化：观察状态依赖关系，看是否能优化空间
6.3 类似题目推荐
LeetCode 213. 打家劫舍 II（房屋围成一圈）
- 解题思路：分解为两个线性问题（偷第一家或不偷第一家）
LeetCode 337. 打家劫舍 III（房屋是二叉树结构）
- 解题思路：树形DP，后序遍历
LeetCode 740. 删除与获得点数
- 解题思路：转化为打家劫舍问题
LeetCode 276. 栅栏涂色（相邻不能同色）
- 解题思路：状态转移类似，但有k种颜色
LeetCode 1981. 最小化目标值与所选元素的差
- 解题思路：类似背包问题的DP
