【动态规划】详解打家劫舍问题不触发警报的最大金额一、题目描述给定一个非负整数数组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为下一步做准备。三、完整代码实现#includevector#includealgorithmusingnamespacestd;classSolution{public:introb(vectorintnums){intnnums.size();// 处理边界情况只有1间房屋时直接返回该房屋金额if(n1){returnnums[0];}// first前i-2间房屋的最高金额初始为第0间intfirstnums[0];// second前i-1间房屋的最高金额初始为前2间的最大值intsecondmax(nums[0],nums[1]);intresultsecond;// 从第3间房屋索引2开始遍历for(inti2;in;i){// 状态转移偷第i间firstnums[i]或不偷second取最大值resultmax(firstnums[i],second);// 更新前两步的状态为下一次遍历做准备firstsecond;secondresult;}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的边界情况。