粉刷房子问题：从DP基础到空间极致优化学习笔记

粉刷房子问题：从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)（仅常数变量，无额外动态数组）

在数据规模较大、内存敏感的场景中，这种滚动更新的写法更贴近实际工程实现。

四、实现细节与工程思考

1. 边界处理
   当房子数量n = 0时直接返回 0，避免数组越界，这是代码鲁棒性的基础。

2. 临时变量的必要性
   更新当前颜色成本时，必须先保存上一轮的三个值，再统一计算新值。如果直接覆盖，会导致后续计算使用已被修改的错误值。

3. 常数级优化的意义
   本题颜色固定为 3 种，状态数极少，滚动变量的写法不仅节省空间，也更利于编译器做寄存器优化，在高频调用、长序列场景下，实际运行效率更稳定。

4. 可扩展性思考
   如果颜色种类从 3 种扩展到k种，思路依然成立：滚动维护k个状态，每次取非自身的k-1个历史状态最小值累加，时间复杂度变为O(n·k)，空间仍为O(k)，依旧是较优的解法。

五、最终实现（C++）

classSolution{public:intminCost(vector<vector<int>>&costs){intn=costs.size();if(n==0)return0;intred=costs[0][0];intblue=costs[0][1];intgreen=costs[0][2];for(inti=1;i<n;++i){intpre_r=red;intpre_b=blue;intpre_g=green;red=min(pre_b,pre_g)+costs[i][0];blue=min(pre_r,pre_g)+costs[i][1];green=min(pre_r,pre_b)+costs[i][2];}returnmin({red,blue,green});}};

六、小结

粉刷房子是非常典型的线性递推+有限状态动态规划问题。
从二维 DP 到滚动变量，本质是只保留对后续有用的历史信息，剔除冗余存储。这种思想在很多空间受限的算法与工程实现中都非常常见，既保证了最优子结构的利用，又在空间与效率上达到了平衡。