粉刷房子问题从DP基础到空间极致优化学习笔记一、问题回顾有n个房子排成一排每个房子可刷红、蓝、绿三种颜色相邻房子颜色不能相同。给定每个房子刷对应颜色的成本矩阵costs[n][3]求粉刷所有房子的最小总成本。约束核心相邻颜色不同目标全局成本最小。这类递推约束最优解结构天然适合动态规划求解。二、常规动态规划思路1. 标准状态定义最直观的方式是定义二维 DP 数组dp[i][0]第i个房子刷红色时前i个房子的最小成本dp[i][1]第i个房子刷蓝色时前i个房子的最小成本dp[i][2]第i个房子刷绿色时前i个房子的最小成本2. 状态转移方程根据颜色互斥约束dp[i][0] min(dp[i-1][1], dp[i-1][2]) costs[i][0]dp[i][1] min(dp[i-1][0], dp[i-1][2]) costs[i][1]dp[i][2] min(dp[i-1][0], dp[i-1][1]) costs[i][2]3. 初始与结果初始dp[0][0] costs[0][0], dp[0][1] costs[0][1], dp[0][2] costs[0][2]结果min(dp[n-1][0], dp[n-1][1], dp[n-1][2])此时时间复杂度O(n)空间复杂度O(n)逻辑清晰但空间存在优化空间。三、空间优化从O(n)到O(1)观察状态转移可以发现计算第i个房子的状态只依赖第i-1个房子的状态与更早历史无关。因此不需要保存完整n×3数组只需要保存上一轮三个颜色的累计成本即可。优化后状态表示用三个变量滚动更新prev_red、prev_blue、prev_green上一个房子对应颜色的最小累计成本curr_red、curr_blue、curr_green当前房子对应颜色的最小累计成本转移逻辑不变只是每次用新值覆盖旧值遍历结束后取三者最小值。优化后时间复杂度O(n)不变空间复杂度O(1)仅常数变量无额外动态数组在数据规模较大、内存敏感的场景中这种滚动更新的写法更贴近实际工程实现。四、实现细节与工程思考边界处理当房子数量n 0时直接返回 0避免数组越界这是代码鲁棒性的基础。临时变量的必要性更新当前颜色成本时必须先保存上一轮的三个值再统一计算新值。如果直接覆盖会导致后续计算使用已被修改的错误值。常数级优化的意义本题颜色固定为 3 种状态数极少滚动变量的写法不仅节省空间也更利于编译器做寄存器优化在高频调用、长序列场景下实际运行效率更稳定。可扩展性思考如果颜色种类从 3 种扩展到k种思路依然成立滚动维护k个状态每次取非自身的k-1个历史状态最小值累加时间复杂度变为O(n·k)空间仍为O(k)依旧是较优的解法。五、最终实现CclassSolution{public:intminCost(vectorvectorintcosts){intncosts.size();if(n0)return0;intredcosts[0][0];intbluecosts[0][1];intgreencosts[0][2];for(inti1;in;i){intpre_rred;intpre_bblue;intpre_ggreen;redmin(pre_b,pre_g)costs[i][0];bluemin(pre_r,pre_g)costs[i][1];greenmin(pre_r,pre_b)costs[i][2];}returnmin({red,blue,green});}};六、小结粉刷房子是非常典型的线性递推有限状态动态规划问题。从二维 DP 到滚动变量本质是只保留对后续有用的历史信息剔除冗余存储。这种思想在很多空间受限的算法与工程实现中都非常常见既保证了最优子结构的利用又在空间与效率上达到了平衡。