空间智能建图算法十年演进（2015–2025）
2026/1/11 23:09:05
“刷房子这点事，怎么就成了动态规划经典题？”——聊透 Paint House 背后的思维方式
说实话，第一次看到「粉刷房子（Paint House）」这道题的时候，很多人内心是抗拒的。
“就刷个房子，还能刷出算法味儿来？”
“这不就是选颜色吗？”
“怎么一写就要 DP？”
但你真做过、真踩过坑之后，就会发现一件事：
这道题表面很生活，骨子里却非常‘工程思维’。
今天我不打算用教科书那套“状态定义 + 转移方程”硬灌你，
而是站在一个写了很多年算法、也写了很多年业务代码的角度，
把 Paint House 这道题掰开揉碎，聊清楚它到底在训练你什么能力。
一、先把题说清楚（不绕弯子）
我们先用大白话描述一下题目（LeetCode 256 / 265 的祖宗版本）：
- 有N 栋房子，排成一排
- 每栋房子可以刷3 种颜色（红、蓝、绿）
- 每种颜色刷每栋房子的成本不同
- 相邻的房子不能刷同一种颜色
- 问：刷完所有房子的最小总成本是多少？
一个典型的输入长这样：<