“刷房子这点事，怎么就成了动态规划经典题？”——聊透 Paint House 背后的思维方式

“刷房子这点事，怎么就成了动态规划经典题？”——聊透 Paint House 背后的思维方式

说实话，第一次看到「粉刷房子（Paint House）」这道题的时候，很多人内心是抗拒的。

“就刷个房子，还能刷出算法味儿来？”
“这不就是选颜色吗？”
“怎么一写就要 DP？”

但你真做过、真踩过坑之后，就会发现一件事：

这道题表面很生活，骨子里却非常‘工程思维’。

今天我不打算用教科书那套“状态定义 + 转移方程”硬灌你，
而是站在一个写了很多年算法、也写了很多年业务代码的角度，
把 Paint House 这道题掰开揉碎，聊清楚它到底在训练你什么能力。

一、先把题说清楚（不绕弯子）

我们先用大白话描述一下题目（LeetCode 256 / 265 的祖宗版本）：

• 有N 栋房子，排成一排
• 每栋房子可以刷3 种颜色（红、蓝、绿）
• 每种颜色刷每栋房子的成本不同
• 相邻的房子不能刷同一种颜色
• 问：刷完所有房子的最小总成本是多少？

一个典型的输入长这样：<