打家劫舍问题的动态规划解法与性能优化笔记一、问题背景回顾给定一个非负整数数组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 基础实现#includevector#includealgorithmusingnamespacestd;classSolution{public:introb(vectorintnums){intnnums.size();if(n0)return0;if(n1)returnnums[0];// 定义dp数组存储前i间房屋的最大金额vectorintdp(n);dp[0]nums[0];dp[1]max(nums[0],nums[1]);for(inti2;in;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 优化后实现#includevector#includealgorithmusingnamespacestd;classSolution{public:introb(vectorintnums){intnnums.size();if(n1){returnnums[0];}// 初始化前两步状态intfirstnums[0];intsecondmax(nums[0],nums[1]);intresultsecond;for(inti2;in;i){// 状态转移偷或不偷当前房屋取最大值resultmax(firstnums[i],second);// 更新状态为下一次遍历做准备firstsecond;secondresult;}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基础解法的数组开销可忽略此时优先保证代码可读性若输入规模极大如百万级房屋数据空间优化能显著降低内存占用避免内存溢出此时状态压缩是必要选择。总结打家劫舍问题的核心是利用动态规划的最优子结构特性通过前序子问题的解推导当前最优解基础解法通过dp数组实现空间复杂度为O(n)利用“状态仅依赖前两步”的特征可通过两个变量替代dp数组将空间复杂度优化至O(1)且不影响时间效率工程实现中需关注边界条件、变量初始化等细节同时结合实际场景权衡性能优化与代码可读性的关系保证代码的鲁棒性和可维护性。