面试必看：打家劫舍
【动态规划】详解打家劫舍问题（不触发警报的最大金额）
一、题目描述
给定一个非负整数数组nums，数组中的每个元素代表对应房屋存放的金额。小偷偷窃时需遵守规则：不能偷窃相邻的两间房屋（否则警报会触发）。请计算在不触动警报的情况下，小偷一夜之间能偷窃到的最高金额。
二、解题思路分析
这是一道典型的动态规划问题，核心特征是“当前最优解依赖于前序子问题的解”，具体分析如下：
问题核心
对于第i间房屋，有两种选择：偷或不偷。- 偷：则第
i-1间房屋不能偷，最高金额为“前i-2间房屋的最高金额 + 第i间房屋的金额”； - 不偷：则最高金额等于“前
i-1间房屋的最高金额”。
最终取两者中的较大值，即为前i间房屋的最优解。
- 偷：则第
优化空间的动态规划思路
常规动态规划会用数组存储每一步的结果，但本题可发现：计算第i间房屋的最优解仅需前两步的结果，因此无需额外数组，只需两个变量即可：first：表示前i-2间房屋能偷到的最高金额；second：表示前i-1间房屋能偷到的最高金额。
遍历从第3间房屋（索引为2）开始，每次通过max(first + nums[i], second)计算当前最优解，再更新first和second为下一步做准备。
三、完整代码实现
#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:introb(vector<int>&nums){intn=nums.size();// 处理边界情况：只有1间房屋时，直接返回该房屋金额if(n==1){returnnums[0];}// first：前i-2间房屋的最高金额（初始为第0间）intfirst=nums[0];// second：前i-1间房屋的最高金额（初始为前2间的最大值）intsecond=max(nums[0],nums[1]);intresult=second;// 从第3间房屋（索引2）开始遍历for(inti=2;i<n;i++){// 状态转移：偷第i间（first+nums[i]）或不偷（second），取最大值result=max(first+nums[i],second);// 更新前两步的状态，为下一次遍历做准备first=second;second=result;}returnresult;}};四、复杂度分析
时间复杂度：O(n)
仅需遍历一次数组（从索引2到末尾），遍历次数与房屋数量n成正比，因此时间复杂度为线性级别。空间复杂度：O(1)
全程仅使用了first、second、result等有限个变量，未开辟额外的数组或容器，空间开销为常数级。
五、补充说明
- 代码中优先处理了
n == 1的边界情况，避免后续对nums[1]的访问越界； - 初始时
second取max(nums[0], nums[1])，是因为前两间房屋只能选其中金额更高的那一间； - 这种用变量代替数组的写法，是动态规划的“空间优化”技巧，在仅依赖前有限步结果的场景中非常实用。
总结
- 打家劫舍问题的核心是“不能偷相邻房屋”，每一步的最优解仅依赖前两步的结果，具备最优子结构特性；
- 用
first和second两个变量代替传统DP数组，可将空间复杂度从O(n)优化至O(1)，状态转移核心为max(first + nums[i], second)； - 时间复杂度为O(n)，是该问题的最优解法，需注意处理房屋数量为1的边界情况。