做了这么多年算法题也带过不少人入门动态规划我越来越觉得有一件事特别反直觉真正把大家领进 DP 大门的往往不是那些看起来“高大上”的题反而是像“刷房子”这种读起来像小学应用题的东西。一排房子三种颜色相邻不能一样买油漆花的钱还不一样——就这么点事怎么就成了 LeetCode 上的经典题、面试里的常客、各路题单上的钉子户原因很简单它是把动态规划的骨架——状态怎么设计、转移怎么推导、边界怎么处理——暴露得最彻底的一道题。它没有复杂的图结构没有棘手的字符串匹配连数据范围都温柔得不行。正因为这层“简单”它才适合用来搞懂一件最核心的事你到底该怎么把一个决策问题翻译成一行行状态转移方程。这篇文章没有打算只讲题解我想把这道题拆开揉碎聊聊它背后的思维方式以及为什么“只关心上一栋房子刷了什么颜色”这一句话就足以改变你对整个动态规划的认知。无论你是刚开始刷题的新手还是已经做过不少 DP 题想回头补基础的老手这篇都值得花几分钟慢慢看。1. 先把这个题目的“表面”看透它到底在问什么1.1 三行描述背后的约束条件先还原一下问题的原始轮廓有一排房子共 n 栋每栋房子可以刷成红色、蓝色或绿色三种颜色中的一种每栋房子刷每种颜色的成本不同。要求是相邻两栋房子不能刷成同一种颜色问把所有房子刷完的最小总成本是多少。题目本身不复杂复杂的是“相邻不同色”这个约束。很多人第一次见到它第一反应是“那我就每栋选最便宜的颜色不就行了吗”然后马上撞上一堵墙假设第一栋最便宜的是红色第二栋最便宜的还是红色但第二栋不能刷红色只能退而求其次刷蓝色或绿色。这个“退而求其次”多付出的差价可能会影响后面所有房子的选择。我举个例子三栋房子成本如下列的顺序是红、蓝、绿房子红色蓝色绿色第1栋1100100第2栋1100100第3栋1001100如果只看每一栋红色对前两栋都是最便宜的但第一栋刷红、第二栋就必须在蓝绿里选一个于是第二栋只能花 100第三栋此时可以刷蓝花 1。总成本是 1 100 1 102。但最优解其实是让第一栋刷红1、第二栋刷绿100、第三栋刷蓝1之外还有一个更妙的方案第一栋刷红1、第二栋刷蓝100、第三栋刷绿100也要 201等等重新看一下——其实最优应该是第一栋红1、第二栋绿100、第三栋蓝1总成本 102 并不好。再看另一种配色第一栋蓝100、第二栋红1、第三栋蓝100总成本 201也不行。反而是第一栋红1、第二栋蓝100、第三栋绿100是 201。那这组数据的最优到底是多少第一栋红 1第二栋绿 100第三栋只能红或蓝蓝是 1合计 102。可是第一栋如果选蓝 100第二栋红 1第三栋蓝 1合计也是 102。似乎 102 是最优了。但这说明什么说明“每栋选最便宜”的局部最优在第一、第二栋之间就得被迫调整而调整的代价是连锁的不是一个简单的“缺什么补什么”能算清楚的。1.2 为什么“每步选最便宜”在这里失灵贪心失效的根本原因在于当前这一步的选择会改变下一步的可行域。这和现实中买东西是一个道理你手里预算有限既要买 A 又要买 BA 的最便宜版本和 B 的最便宜版本可能有冲突比如共用同一个接口、同一个插座你只能委屈其中一个。此时“最便宜”不再是唯一指标还得考虑“我选了这个后面还能不能选到更划算的”。这种“决策之间有耦合”的问题正是动态规划登场的信号。耦合的意思是当前决策的代价不能只从当前这一步来计算还要把这一步对后续选择的影响折算进来。可是“影响”这种东西飘忽不定怎么折算呢这就引出了动态规划最核心的动作——把决策后的“局面”记录下来而不是只记录一个孤零零的累计花费。你刷完第 i 栋房子后真正影响未来的仅仅是你这栋刷了什么颜色。至于前 i-1 栋是怎么刷的、中间绕了多少弯子对于后续决策来说都是历史包袱不影响将来。所以这道题教会我们的第一课就是当一个局部最优的贪心策略被“约束冲突”卡住时别急着换别的贪心而是停下来想想——我需要记录哪些信息才能让未来的决策不再需要翻旧账2. 从暴力到状态动态规划的第一性原理在这里显形2.1 “上一手出了什么”决定了一切动态规划里总说“状态”这个词但很多人对状态的理解停留在“dp 数组下标里存的东西”没有真正体会到它是在描述“一个决策后的局面快照”。我用一个生活化的类比来解释。想象你在玩“剪刀石头布”的连续对局规则是你不能连续两局出同一个手势。那么当你站在第 i 轮准备出手时你需要知道什么只有上一轮出了什么。你不需要记得第一轮出了什么、第二轮怎么赢的、第三轮是怎么被克的——那些全都不影响你这一轮能出什么。于是“上一轮的手势”就是当前局面的最小充分信息这就是状态。刷房子也是一样的。当你在第 i 栋房子前举起刷子决定它刷红、蓝还是绿时历史信息里唯一重要的就是第 i-1 栋刷了什么颜色。因为题目唯一的历史约束就是“相邻不同色”而这个相邻已经缩到了最近的一对。于是 dp 数组的最小状态必然要包含“当前位置”和“当前这栋的颜色”正是这两个维度组合成了我们需要的全部信息。这实际上就是动态规划中“无后效性”的通俗版本未来的决策只依赖当前状态而不依赖达到当前状态的具体路径。理解了这一点状态设计就不再是靠灵感乱猜而是一个有逻辑可循的过程先问自己当我站在某一个时间点上要面向未来做决策我到底必须知道哪些历史信息把这些信息全部塞进状态里状态就设计出来了。2.2 状态定义与转移方程的完整推导下面我们把直觉用数学语言固化下来。定义 dp[i][j] 表示“刷完前 i 栋房子并且第 i 栋房子刷颜色 j 时所需的最小总成本”。其中 j 取值范围是 0、1、2分别对应红、蓝、绿。那么对于第 i 栋如果它刷颜色 j前第 i-1 栋就必须刷另外两种颜色之一于是有转移方程dp[i][j] min(dp[i-1][0], dp[i-1][1], dp[i-1][2] 中所有 k ! j 的项) cost[i][j]写成展开形式就是dp[i][0] min(dp[i-1][1], dp[i-1][2]) cost[i][0]dp[i][1] min(dp[i-1][0], dp[i-1][2]) cost[i][1]dp[i][2] min(dp[i-1][0], dp[i-1][1]) cost[i][2]边界条件非常直观刷第一栋时前面没有房子所以 dp[0][j] cost[0][j]。最终答案就是 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])也就是最后一栋刷任意颜色的最小总成本。这一步的推导看起来平平无奇但它背后有一个很深的逻辑我没有去枚举“前 i-1 栋是怎么刷的”而是只依赖了一个递推关系——前 i-1 栋的最优解已经被完整地存进了 dp[i-1] 里。这就是“最优子结构”在起作用全局最优的尾巴一定也是某个子问题的最优解。2.3 为什么“只关心上一栋”就够用了这句话我想单独拿出来说因为它是理解整道题的关键也是很多人在做 DP 题时最容易卡住的地方。有人会问“虽然相邻不能同色但是第 i-2 栋的颜色会不会间接影响第 i 栋的选择”答案是不会因为这个影响已经被“折叠”进 dp[i-1] 的数值里了。dp[i-1][1] 已经代表了“前 i-1 栋刷完、且第 i-1 栋刷蓝色”这个局面下能取得的最小总成本而这个成本是在“第 i-2 栋不能刷蓝色”的约束下算出来的。它已经内化了第 i-2 栋带来的全部限制。所以当你站在第 i 栋面前时你不需要知道第 i-2 栋到底刷了什么颜色只需要知道“为了让第 i-1 栋刷成蓝色我至少要花多少钱”这就是 dp[i-1][1] 的含义。打个不太严谨但很好记的比方这就像开车导航。当你行驶到某个路口时导航只需要知道“从起点到当前路口的累计最优时间”而不需要知道你前面每一个路口分别等了几个红灯。那些信息全部被压缩成了一个数字。动态规划做的就是不断把“前面所有决策的后果”压缩成一个或几个数字让每一步决策只做局部计算却能保证全局最优。3. 从一维到二维Paint House 如何帮助建立线性 DP 的完整视图3.1 与 01背包、最长上升子序列的横向对比很多人刷题刷到一定阶段会被各大题单里的 DP 题搞得晕头转向原因在于没有把 DP 题的结构抽象出来。Paint House 最好的地方是它给了你一个非常干净的“线性基准”可以与其它经典题对照着理解。题目状态维度转移方式核心难点Paint House位置 颜色从前一位置的不同颜色取最小值状态里必须记录最后一个颜色最长上升子序列位置从所有更小的位置转移需要遍历前驱O(n^2)可优化01背包物品编号 剩余容量选/不选当前物品并减容量容量维度的顺序处理01背包的难点在于“容量”这个维度很抽象选与不选的决策跨越了物品编号。而 Paint House 的难点没有那么高因为它只需要你认识到“颜色”也必须作为状态的一部分然后转移就是简单的“排除同色取最小值”。但两者的思维方式完全一致找到一个足够的信息快照让后续决策不需要翻历史账。带着这个认知再去做 01背包你会发现“剩余容量”正是一个这样的信息快照——它决定了你以后还能装多少东西而不需要知道你具体装了哪些物品。3.2 滚动数组与空间优化的演进路线Paint House 的转移只依赖 dp[i-1] 这一行因此完全没有必要用一个 n×3 的二维数组把全部历史状态存下来。这种“只需要紧邻的上一步”的结构正是滚动数组登场的理想场景。最简单的实现是设三个变量 dp0、dp1、dp2每一轮迭代时用上一轮的旧值计算出新值。需要注意的是计算顺序上不能先覆盖再使用比如你不能先把 dp0 更新成新值然后又拿新的 dp0 去算 dp1那就算错了。正确做法是先把旧值存到临时变量里或者用一个 prev0、prev1、prev2 的拷贝等三个新值全部算完再一次性赋值。下面是一个标准的滚动数组实现def min_cost(costs): if not costs: return 0 prev0, prev1, prev2 costs[0] # 第一栋的三种成本 for i in range(1, len(costs)): cur0 min(prev1, prev2) costs[i][0] cur1 min(prev0, prev2) costs[i][1] cur2 min(prev0, prev1) costs[i][2] prev0, prev1, prev2 cur0, cur1, cur2 return min(prev0, prev1, prev2)这段代码的空间复杂度从 O(n×3) 降到了 O(1)时间复杂度仍然是 O(n)。面试里主动提这一句“我可以只保留上一行的状态”是个非常加分的信号说明你不是死记硬背题解而是真的理解了转移只涉及上一行。3.3 暴力递归、记忆化搜索、迭代 DP同一思路的三副面孔初学者经常被“递归怎么写、迭代怎么写、记忆化是什么”绕晕。实际上这三者完全可以用同一套状态定义串起来。最原始的暴力递归就是枚举所有合法的配色方案类似这样def dfs(i, j): # 返回刷完前 i 栋、且第 i 栋颜色为 j 的最小成本 if i 0: return costs[i][j] # 边界 best float(inf) for k in range(3): if k ! j: best min(best, dfs(i-1, k)) return best costs[i][j]这个递归的问题是会出现大量重复子问题dfs(2, 0) 和 dfs(2, 1) 都会去调用 dfs(1, 2)重复计算很多。加一个缓存就变成记忆化搜索from functools import lru_cache lru_cache(None) def dfs(i, j): if i 0: return costs[i][j] return costs[i][j] min(dfs(i-1, k) for k in range(3) if k ! j)当你把递归的方向反过来从 i 小的往 i 大的推就得到了前面的迭代 DP。三者的本质完全一致只是计算的顺序不同。这个认知非常重要因为很多 DP 难题在思维上其实更接近记忆化搜索迭代写法只是把递归展开了而已。能在这个简单的题上把三者打通后面遇到复杂 DP 会省很多力气。4. 从刷房子到刷世界Paint House 的模型迁移与变形4.1 变体一Paint House IIK 种颜色的复杂度优化LeetCode 265 是这道题的常见升级版把三种颜色改成 K 种颜色。此时状态定义变成 dp[i][j] 表示第 i 栋刷第 j 种颜色的最小成本转移方程变成dp[i][j] min(dp[i-1][k] for k ! j) costs[i][j]如果直接实现每一栋的每一种颜色都要遍历 K-1 个前驱总复杂度是 O(n×K^2)。当 K 比较大的时候这个复杂度就很尴尬了。但这里面藏着一个非常经典的优化也是很多进阶题目的雏形对于同一栋房子 i所有颜色共享同样的“前驱最小值”信息。我们只需要提前算出 dp[i-1] 这 K 个数中的最小值和次小值以及最小值对应的颜色编号。那么对于第 j 种颜色如果 j 不是最小值所在的颜色那么 min(dp[i-1][k] for k ! j) 就是那个全局最小值。如果 j 正好是最小值所在的颜色那么前驱里必须排除它自己只能取次小值。这样一来每一栋只需要 O(K) 的时间来更新总复杂度降到了 O(n×K)。这个“维护最小值和次小值”的技巧在无数后续 DP 题里都会反复出现值得深刻记住。4.2 变体二首尾相联环形房子的通用处理套路如果题目再加一条“第一栋和最后一栋也不能同色”那就变成了环形问题。坊间流传的通用做法是“枚举第一栋的颜色然后分别跑两遍线性 DP”。具体来说如果第一栋固定刷颜色 j那么最后一栋就不能刷颜色 j。在计算终态时排除颜色 j 取最小值即可。由于颜色只有三种可以简单做三次扫描也可以推广到 K 种颜色时做 K 次扫描总体复杂度乘以颜色数。我更喜欢把它理解成“把环砍成一条链然后用边界条件模拟相邻关系”。很多环形 DP 题比如打家劫舍 II用的都是同一招。这里的关键不是背模板而是明白环带来的额外约束本质上是给首尾之间加了一条“伪相邻”的边通过枚举首状态就把它转化成了等价的线性问题。4.3 现实中到底哪里会用到这个模型你可能会想谁会真的去刷一排房子还纠结相邻颜色但在实际工程和决策场景里这个模型出现的频率远超想象。举两个例子。第一个是排班问题。假设你要给一个连续营业的柜台排班每个员工可以上早班、中班、晚班相邻两天不能安排同一个员工上同一班次每个员工在不同班次的成本比如人力成本、加班费不同问一周下来最小总成本。这就是加了班次数量约束后的 Paint House 直接映射。第二个是多阶段项目资源分配。比如一条生产流水线上每个阶段选一种工艺相邻工位不能选相同工艺以避免干扰每个工艺在不同工位的成本不同求全局最小成本。本质上也是同一套线性 DP 骨架。所以这道题能进入 hot100、挤进洛谷 DP 题单的头部不是因为它难而是因为它的模型太基础、太可迁移了。理解了这个模型你再去看“车辆动态规划问题”里的路径分段、去看 01背包的取舍决策、去看线性 DP 家族会发现大家都是同一种思维方式的不同皮肤定义信息快照写出转移关系处理好边界。5. 实际编码中的心路历程与排查技巧5.1 三种常见错误与调试实录这道题虽然简单但我在带人刷题的过程中见过不少在简单题上翻车的案例。最常见的有三类。第一类是边界写错。有人习惯把 dp 数组初始化为 0然后从 i1 开始循环却忘了把第一栋房子的成本赋值进去导致结果少了第一栋的花费。这类问题在答案错误时很容易定位把 n1 的样例跑一下应该返回 costs[0] 的最小值如果返回 0 就说明边界有 bug。第二类是转移时没有排除上一个颜色。有时候图省事直接写 dp[i][j] min(dp[i-1]) cost[i][j]这会让相邻两栋刷同色计算结果可能反而是更小的造成答案偏小。这种 bug 在代码 review 时不仔细看很难发现因为结果看起来“合理”。第三类是滚动数组的覆盖顺序问题。在更新 dp0、dp1、dp2 时如果直接原地赋值比如先算 cur0 然后把 prev0 覆盖成 cur0再拿这个新的 prev0 去算 cur1就会把转移关系搞乱。解决办法是临时变量一次性替换。5.2 推荐的自查方法对拍与打印我强烈建议你在练习时哪怕题目再简单也写一个暴力枚举的对照函数在小规模数据上做随机对拍。以这道题为例暴力枚举可以用三层循环穷举所有配色检查相邻不同色之后取最小值然后把结果和 DP 版的结果做比对。随机生成几十组 n 很小的成本数组跑一遍代码逻辑对不对一目了然。另外调试 DP 题最好用的手段就是打印状态表。每一轮迭代结束把 dp 数组目前的值打出来用笔在纸上追踪一遍转移过程。很多时候你以为懂了转移方程但用手推两个样例后就会发现某个下标写错了或者 min 的目标选错了。我在线下带人时经常说一句话“不要怕打印多怕的是你只看结果不看过程。” 打印状态表看起来笨但它能帮你建立对状态转移的直觉这种直觉比背一百道题都更有用。5.3 面试和讲解时的表达要点如果你在面试中遇到这道题除了把代码写对怎么讲也非常重要。我建议按这个顺序讲第一步说清楚状态是什么“我准备用一个二维数组 dp[i][j] 表示刷完前 i 栋且第 i 栋刷第 j 种颜色的最小成本因为对未来决策唯一重要的信息就是最后一栋颜色。”第二步说清楚转移为什么是这样“当前颜色固定后前一栋只能选另外两种颜色所以从上一行的两个值里取最小值再加上当前颜色成本。”第三步说清楚边界和答案“第一栋直接取三种颜色的成本作为初值答案取最后一栋三种颜色的最小值。”第四步主动提优化“因为每一行只依赖上一行所以可以用滚动变量把空间降到 O(1)。”这套话术没有一个字是废话每一句都在向面试官展示你理解了问题结构。我自己在模拟面试时特别喜欢听对方说出“因为未来只依赖当前颜色所以我需要把颜色作为状态的一部分”这句话它说明这个人不是背题而是在用动态规划的思维思考问题。另外有一个小技巧讲完思路后用一个极小的例子口算验证一下。比如 n2、成本是 [[1,2,3],[3,2,1]]你可以快速算出最优是 2第一栋刷红 1、第二栋刷蓝 1总成本 2等一下红 1 加蓝 1 是 2但第一栋红 1、第二栋只能是蓝或绿蓝 2、绿 1所以第二栋绿 1总成本 2如果第一栋绿 3第二栋红 3总成本 6所以最优确实是 2。能把这种手算过程流畅表达出来比背一段漂亮的代码更能打动面试官。最后说一点我在实际刷题多年后的体会。很多人觉得动态规划是一座大山但每次刷完一道题如果不去琢磨“状态为什么这么设计”很快就会全忘光。刷房子这道题之所以经典恰恰是因为它简单到让你没有借口跳过“为什么”也清晰到让你想忘都忘不掉那个状态定义。我甚至会建议每个刚开始接触动态规划的人把这道题、滚动数组的写法、以及 Paint House II 的最小值次小值优化串起来做三遍。第一遍写对第二遍优化空间第三遍徒手推导转移并把它讲给别人听。这三遍下来你对线性 DP 的理解会上一个台阶。以后无论你是在洛谷题单上刷题还是做 hot100 里的动态规划题都会感谢自己在这个“看似简单”的题上花的时间。