别被“k 种颜色”吓住：粉刷房子 II，其实是在教你怎么把 DP 做到又快又优雅

别被“k 种颜色”吓住：粉刷房子 II，其实是在教你怎么把 DP 做到又快又优雅

如果你刷过 LeetCode，看到Paint House II（粉刷房子 II）这个题，大概率第一反应是：

“嗯？房子 n 个，颜色 k 种，还不能相邻同色？
这 DP 怕是要 n * k * k 了吧？”

然后一算复杂度，直接皱眉头。

但说句掏心窝子的话：
这道题真正想教你的，不是 DP 本身，而是——如何在“看似爆炸”的状态里，抓住最关键的那一点信息。

今天我就用Echo_Wish的方式，跟你像平时聊天一样，把这道题讲透。

一、先把题翻译成人话

题目描述（人话版）：

• 有n栋房子排成一排
• 每栋房子可以刷k种颜色
• 相邻的房子颜色不能一样
• costs[i][j]表示第i栋房子刷第j种颜色的成本
• 问：刷完所有房子，最小总成本是多少？

是不是很像一道“老 DP 题”？
是的，但它的坑在于：k 是变量，而