打家劫舍问题的动态规划解法与性能优化笔记

打家劫舍问题的动态规划解法与性能优化笔记

一、问题背景回顾

给定一个非负整数数组nums，每个元素代表对应房屋存放的金额，要求在不偷窃相邻房屋（避免触发警报）的前提下，求解能偷窃到的最大金额。这一问题的核心是在约束条件下寻找最优解，具备动态规划问题典型的“最优子结构”特征——当前位置的最优解可由前序子问题的解推导而来。

二、基础解法：常规动态规划思路

2.1 状态定义与转移

首先从最直观的动态规划思路入手，定义dp[i]表示前i间房屋能偷窃到的最大金额。对于第i间房屋，存在两种选择：

• 偷第i间：则第i-1间不能偷，此时dp[i] = dp[i-2] + nums[i]；
• 不偷第i间：此时dp[i] = dp[i-1]。

因此状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

2.2 基础实现

#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:introb(vector<int>&nums){intn=nums.size();if(n==0)return0;if(n==1)returnnums[0];// 定义dp数组存储前i间房屋的最大金额vector<int>dp(n);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(inti=2;i<n;i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}returndp[n-1];}};

2.3 基础解法分析

• 时间复杂度：O(n)，需遍历数组一次完成状态转移；
• 空间复杂度：O(n)，需维护一个长度为n的dp数组存储中间状态。

这一解法逻辑清晰，符合动态规划的常规思路，能正确解决问题，但在数据规模较大时，数组的空间开销会成为可优化的点。

三、空间优化：压缩状态存储

3.1 优化思路

观察状态转移方程可发现，计算dp[i]仅依赖dp[i-1]和dp[i-2]两个值，无需保存完整的dp数组。因此可使用两个变量替代数组，分别记录前两步的状态：

• first：对应dp[i-2]，即前i-2间房屋的最大金额；
• second：对应dp[i-1]，即前i-1间房屋的最大金额。

遍历过程中只需不断更新这两个变量，即可推导出当前的最优解，无需额外存储所有中间状态。

3.2 优化后实现

#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:introb(vector<int>&nums){intn=nums.size();if(n==1){returnnums[0];}// 初始化前两步状态intfirst=nums[0];intsecond=max(nums[0],nums[1]);intresult=second;for(inti=2;i<n;i++){// 状态转移：偷或不偷当前房屋，取最大值result=max(first+nums[i],second);// 更新状态，为下一次遍历做准备first=second;second=result;}returnresult;}};

3.3 优化后分析

• 时间复杂度：仍为O(n)，遍历次数未发生变化；
• 空间复杂度：优化为O(1)，仅使用有限个变量，空间开销与输入规模无关。

这一优化是动态规划问题中“状态压缩”的典型应用，在仅依赖前有限步状态的场景中，能显著降低空间占用，且不会增加时间成本。

四、工程实现的细节考量

4.1 边界条件处理

代码中优先处理n == 1的情况，避免后续访问nums[1]时出现数组越界。在工程实现中，边界条件的处理是保证代码鲁棒性的关键——实际场景中输入规模可能存在极端情况（如空数组、单元素数组），需提前预判并规避异常。

4.2 变量初始化的合理性

初始时second取max(nums[0], nums[1])，符合“前两间房屋只能选金额更高者”的逻辑，这一初始化方式既贴合问题规则，也为后续遍历奠定了正确的初始状态。在工程开发中，变量初始化的合理性直接影响后续逻辑的正确性，需与问题的实际约束一致。

4.3 代码可读性与可维护性

优化后的代码未因追求性能而牺牲可读性：变量命名（first/second）直观反映其对应的状态含义，核心逻辑（状态转移、变量更新）分步骤实现，便于后续调试和扩展。例如，若问题扩展为“房屋环形排列”（首尾房屋也不能同时偷），仅需在现有逻辑基础上稍作调整，即可适配新场景。

五、进一步的思考

5.1 时间复杂度的上限

该问题的时间复杂度已达到O(n)，这是理论上的最优值——因为要确定每间房屋的选择策略，必须遍历所有房屋至少一次，无法通过算法优化进一步降低时间复杂度。

5.2 状态压缩的适用场景

状态压缩并非适用于所有动态规划问题，其核心前提是“当前状态仅依赖有限的前序状态”。例如，若问题约束变为“不能偷相邻的三间房屋”，则需保存前三个状态，但仍可通过变量替代数组实现空间优化；而若状态依赖的前序步骤数与输入规模成正比，则状态压缩无实际意义。

5.3 实际应用中的权衡

在工程实践中，空间优化的优先级需结合实际场景判断：

• 若输入规模较小（如房屋数量少于1000），基础解法的数组开销可忽略，此时优先保证代码可读性；
• 若输入规模极大（如百万级房屋数据），空间优化能显著降低内存占用，避免内存溢出，此时状态压缩是必要选择。

总结

1. 打家劫舍问题的核心是利用动态规划的最优子结构特性，通过前序子问题的解推导当前最优解，基础解法通过dp数组实现，空间复杂度为O(n)；
2. 利用“状态仅依赖前两步”的特征，可通过两个变量替代dp数组，将空间复杂度优化至O(1)，且不影响时间效率；
3. 工程实现中需关注边界条件、变量初始化等细节，同时结合实际场景权衡性能优化与代码可读性的关系，保证代码的鲁棒性和可维护性。