从粉刷房子看线性dp：状态设计与优化的完整拆解-北京尧图网络

如果你正在按动态规划题单刷题大概率会在前二三十题的位置遇到“粉刷房子”。这道题的标签是dp、线性动态规划题目本身很短官方解法也不长但很多人的困境非常一致答案看一眼就懂合上代码自己写却不知道 dp 数组为什么长这样、转移方程是怎么推出来的。这篇文章就把这条链路完整拆一遍从读题建模、状态设计、代码实现到扩展优化最后再串一下刷题群里经常出现的树形dp、单调队列优化dp这些热词。适合刚开始学动态规划的新手也适合准备面试想系统梳理线性dp模型的同学。1. 粉刷房子到底在考什么题面拆解与破题思路1.1 题面长什么样从文字到数学模型先明确题目本身。假设有一排房子共 n 个每个房子可以被粉刷成红色、蓝色、绿色三种颜色中的任意一种。约束只有一个相邻的两个房子颜色不能相同。给你一个 n 行 3 列的花费矩阵 cost其中 cost[i][0] 表示第 i 个房子刷成红色的成本cost[i][1]、cost[i][2] 分别是蓝色和绿色的成本。要求算出粉刷所有房子的最小总花费。这道题表面看是在处理“颜色的排布”实际翻译成数学语言是在长度为 n 的序列上每个位置有 3 种取值相邻两个取值不能相等每个取值有对应代价求代价最小的合法序列。这就是一个非常标准的线性 dp 问题——问题结构是一条线决策是一个接一个做出来的每一步只受相邻位置约束。很多初学者第一步就想贪心每个房子选最便宜的颜色遇到和前一间冲突就换一个次便宜的。但这类“局部最优叠加成全局最优”的直觉在这道题里是错的。原因很简单你在第 i 个房子省下的几块钱可能在后面的房子里造成连锁反应逼迫连续选贵的颜色。1.2 为什么不能直接贪心一个反例就够了用一个两行的小例子就能说明白。假设花费矩阵是cost [[2, 1, 1], [1, 100, 100]]如果贪心房子 0 选最便宜的颜色 1花费 1房子 1 因为不能和房子 0 同色只能在颜色 0 或 2 里选两个都要 100总花费 101。但最优方案是房子 0 选颜色 0花费 2房子 1 选颜色 1花费 1总花费 3。差出 98 块钱。从这个例子能看明白贪心只看到当前这一步而这道题的决策有“后效前的约束”——你现在选了什么会影响你下一步能选什么。所以需要一个能同时记住“当前累计花费”和“当前房子颜色”的思考方式这就是 dp。1.3 状态的定义是这类题的灵魂动态规划里最常听到的一句话是“dp 状态怎么定决定这道题难不难”。粉刷房子的状态定义非常典型我建议原样背下来dp[i][j] 表示粉刷完前 i 个房子下标 0 到 i并且第 i 个房子刷的是颜色 j 时累计的最小花费。这里有三个重点要解释清楚。第一为什么 dp 数组要带颜色维度因为约束是“相邻不能同色”如果状态里不记录最后一个房子的颜色下一步转移时就不知道该排除哪个颜色整个递推就断了。状态里存什么取决于下一步转移需要知道什么。这是一个通用经验。第二i 表示的是“处理到第几个房子”j 表示颜色j 的取值只有 0、1、2。注意这里不是“前 i 个房子的全局最小花费”因为全局最小花费这个信息不足以支撑我们把第 i1 个房子接上去。第三dp 的价值是“用空间换时间”。暴力枚举所有颜色序列是 3^n 种指数爆炸但 dp 把每个位置每种颜色下的最优花费都记下来让后面的状态可以直接复用前面的计算结果总状态量只有 O(n * 3)。状态定义想明白之后转移方程其实水到渠成这也是下一节要展开的内容。2. 从暴力递归到状态转移方程dp 是怎么“想”出来的2.1 暴力搜索为什么指数爆炸先看最直觉的写法。假设定义一个递归函数dfs(i, prev_color)表示当前要决定第 i 个房子的颜色且第 i-1 个房子颜色是 prev_color 时的最小花费。函数内部枚举 i 位置所有不等于 prev_color 的颜色取最小值递归下去。def dfs(i, prev_color): if i n: return 0 best float(inf) for c in range(3): if c ! prev_color: best min(best, dfs(i 1, c) cost[i][c]) return best这个写法在 n 很小的时候能跑但复杂度是 O(3^n)。每一层递归都要尝试 2 到 3 个分支n 越大越不可收拾。问题在于同一个状态(i, prev_color)会在不同的递归路径里被反复计算做了大量重复工作。动态规划其实就是把这个递归的过程反过来先算最底层的小问题再用小问题的答案递推大问题并且把每个子问题的答案存下来。换句话说dp 是自底向上的记忆化搜索。2.2 状态转移方程的推导过程现在从状态定义出发推转移。既然 dp[i][j] 表示“第 i 个房子刷颜色 j 的最小总花费”那它从哪里来显然是从第 i-1 个房子转移过来的而且第 i-1 个房子的颜色不能等于 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]翻译成大白话如果第 i 个房子要刷红色那么前一个房子只能刷蓝色或绿色我从前一个房子刷蓝色或绿色这两种状态里挑一个更省钱的再加上当前房子刷红色的花费就是“当前房子为红色”的最小总花费。初始条件也很直白第 0 个房子前面没有房子没有相邻约束所以dp[0][0] cost[0][0] dp[0][1] cost[0][1] dp[0][2] cost[0][2]最终答案是处理完所有房子后最后这个房子刷成任意一种颜色都行所以取min(dp[n-1][0], dp[n-1][1], dp[n-1][2])。整个过程可以这样理解我们不是一次性做 n 个决策而是把“刷前 i 个房子”这个大问题拆成“刷前 i-1 个房子”的小问题再接上第 i 个房子的选择。每一步都只保留每种约束下最优的累计结果把指数级的可能性压缩成线性的计算量。2.3 最优子结构与无后效性用大白话讲透新手看题解最怕看到这两个名词我试着用粉刷房子把它们讲明白。最优子结构的意思是全局最优解可以由子问题的最优解拼出来。在粉刷房子里如果整个方案是最优的那么去掉最后一个房子后前 n-1 个房子的方案也一定是最优的。假如前 n-1 个房子存在一个更优的方案那我把那个方案接上新房子总花费会更低这和“原方案最优”矛盾。所以大问题的最优解一定包含小问题的最优解。无后效性的意思是过去的选择已经凝固不会影响未来的决策未来只关心当前状态的值。在这道题里dp[i][j] 已经包含了“前 i 个房子、最后颜色为 j”的全部信息我们在计算 dp[i1][k] 时只需要知道 dp[i][j] 的数值不需要知道 dp[i][j] 背后那些房子具体刷了什么颜色。历史细节被压缩成一个状态值这就是无后效性。这两个性质并不只是考试名词它们才是判断一道题能不能用 dp 的试金石。你拿到一道新题可以先试着问自己大问题的最优解包含子问题的最优解吗优化目标能用一个状态值概括并且转移时只需要看一个或几个固定前置状态吗如果都是这道题基本就是 dp 题。3. 代码实现与细节控制把算法变成能跑的代码3.1 直观版二维 dp 数组实现先用最容易理解的方式写一遍把状态和转移直接落到代码上def min_cost(cost): n len(cost) if n 0: return 0 # dp[i][j]刷完前 i 个房子且第 i 个房子颜色为 j 时的最小花费 dp [[0, 0, 0] for _ in range(n)] # 初始化第一间房子 dp[0] cost[0][:] for i in range(1, n): 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] return min(dp[n - 1])这里有一个小细节dp[0] cost[0][:]而不是dp[0] cost[0]。直接用等号赋值的话dp[0] 和 cost[0] 就指向同一个列表后面如果因为某种方式修改 dp[0]会连带把原始数据改掉增加调试难度。用切片拷贝一份是最稳妥的。时间复杂度是 O(n)只遍历一次数组空间复杂度是 O(n) 的 dp 表实际上每行只有 3 个数字n 大的时候这里其实有优化空间。3.2 优化版滚动数组把空间降为 O(1)观察转移方程可以发现计算 dp[i] 这一行时只用到了 dp[i-1] 这一行更早的 dp 表数据全都用不到了。既然这样完全没有必要把整张表存下来只需要两个数组来回倒就行这叫滚动数组。def min_cost_optimized(cost): n len(cost) if n 0: return 0 prev cost[0][:] for i in range(1, n): cur [0, 0, 0] cur[0] min(prev[1], prev[2]) cost[i][0] cur[1] min(prev[0], prev[2]) cost[i][1] cur[2] min(prev[0], prev[1]) cost[i][2] prev cur return min(prev)空间复杂度从 O(n) 降到了 O(1)因为不管房子有多少我们始终只保留上一行的三个数字和当前行的三个数字。这里的核心思想是“能滚动就滚动”只要状态转移严格依赖前一步并且历史状态不再被访问就没有必要把过程全部记下来。这份代码在 LeetCode 和绝大部分在线评测系统上都能直接跑通。如果你在面试里写出来面试官通常会追问一句“能不能优化空间”这段滚动数组代码就是标准答案。3.3 千万别直接改原数组一个容易踩的坑有些同学会把 dp 数组直接复用 cost在当前行上原地更新。第一次写很容易这样# 错误示例 for i in range(1, n): cost[i][0] min(cost[i-1][1], cost[i-1][2]) cost[i][0] cost[i][1] min(cost[i-1][0], cost[i-1][2]) cost[i][1] cost[i][2] min(cost[i-1][0], cost[i-1][1]) cost[i][2]这个写法的问题是计算cost[i][1]和cost[i][2]时cost[i][0]已经被覆盖成新值了如果某个后面还要读旧cost[i][0]就会出错。仔细看上面的式子cost[i][1]的计算只用了cost[i-1]的上一行没有用到当前行其他列所以这一题运气好原地更新其实也能过。但这是个坏习惯换一道状态之间互相引用的题原地更新就会算错。提示dp 数组最好和原始输入数据分开维护。尤其是状态转移里同一行不同列还要互相参考时原地更新几乎是 bug 之源。4. 常见错误与排查技巧实录4.1 答案到底取最大值还是最小值问出这个问题的多半是把这道题和“打家劫舍”搞混了。粉刷房子求的是最小花费最终答案必然是min这是题目语义决定的。如果你的答案总是比预期大可以检查一下 dp 数组有没有被初始化为 0 而不是正确的基础花费或者转移时用了min却把累加写成负号的低级错误。一个非常实用的自测方法是把cost换成全 1 矩阵答案应该是 n因为每间房子花费都是 1不管怎么选总花费都是 n。再用 1.2 节的反例手动验一遍能强制发现是不是初始化错了。4.2 边界情况n 等于 0 和 n 等于 1LeetCode 的输入有时候会给你n 0或者n 1这两种情况最容易忽略。n 0没有房子总花费是 0直接返回 0。n 1只有一间房子没有任何相邻约束选三种颜色里最便宜的那个就行即min(cost[0])。对应的代码在 3.1 节里已经覆盖了 n0 的情况dp[0]也能正确处理 n1但如果你是单独判断的人要注意 dp 数组长度为 0 时不能去访问dp[0]会直接越界报错。写完代码后建议一定把这三种情况跑一遍[[1,2,3]]n1和[]n0实测下来很多一眼对的代码在[]上都会崩。4.3 颜色数量变成 k 时如何优化到 O(nk)题目最常见的变体是把 3 种颜色改成 k 种颜色状态定义和转移方程依然成立只是从三个式子变成一个循环dp[i][j] min(dp[i-1][m]) cost[i][j] # 其中 m ! j朴素做法是对于每个 j 遍历所有 m复杂度 O(n * k * k)当 k 到几百几千时就会超时。优化的办法是维护上一行的最小值和次小值如果最小值对应的颜色不是 j那直接取最小值如果正好是 j就退而取次小值。这样每个位置只需要 O(1) 就能算出排除当前颜色后的最优前置状态整体复杂度降到 O(n * k)。伪代码如下for i in range(1, n): # 从 prev 中找出最小值和次小值以及最小值的颜色下标 idx # 计算 cur 时 for j in range(k): if j ! idx: cur[j] min_val cost[i][j] else: cur[j] second_min cost[i][j]这个“维护最小值和次小值”的技巧在 dp 优化里非常常用尤其是状态中带“排除当前项”的题目以后刷单调队列优化dp、树形dp 时也经常借这个思想。4.4 房子排成环形怎么办固定首间枚举即可另一个高频变体是房子不是一排而是一个环第一间和最后一间也不能同色。比如 LeetCode 213 打家劫舍 II 就是这个改法。处理思路是枚举第一间房子的颜色。第一间房子只有 3 种颜色或 k 种分别固定它为颜色 c跑一次标准线性 dp但初始化时只把dp[0][c]设为cost[0][c]其他颜色设为无穷大。转移照常最后取最后一间房子颜色不等于 c 的最小值。一共跑 3 次或 k 次取全局最小答案就出来了。n 1 时环形没有意义因为只有一个房子不存在两个端点互斥的问题直接返回min(cost[0])即可。这类“固定开头状态枚举开头取值”的方法在线性 dp 里是解决环状约束的通用套路。5. 从粉刷房子到完整的 dp 模型图鉴5.1 线性 dp 的通用识别套路刷完粉刷房子值得停下来总结一下线性 dp 的共性问题长什么样。它们通常有一个天然的顺序结构一排房子、一个数组、一条时间轴、一个字符串下标。状态可以看成“处理到第 i 个元素时某种约束下的最优值”转移发生在相邻位置之间而且大多数只需要依赖前一个或前两个状态。识别方法可以提炼成三句话问题有没有明确的顺序有大概率是线性 dp。每个位置的决策会不会影响相邻位置的合法性会那状态里多半要带上“当前选择是什么”。当前最优值能不能由前面某个位置的某种状态直接推出来能就把它写成转移方程。粉刷房子是“当前位置颜色影响相邻合法性”的典型代表。你看打家劫舍也是这个结构每个房子偷或不偷同样影响邻居是否合法。这就是为什么我强烈建议这道题要彻底弄懂而不是背掉它代表了一整类状态设计思路。5.2 几道和粉刷房子“长得像”的兄弟题刷题有体系很重要做完粉刷房子后可以立刻去做下面几道题对比状态设计上的异同题目状态设计和粉刷房子的关系打家劫舍dp[i] 或 dp[i][0/1]偷/不偷同样是相邻互斥只是颜色从 3 种变成 2 种打家劫舍 II环形数组拆成两组线性 dp和环形粉刷房子解法思路一致买卖股票的最佳时机含冷冻期状态是持有/空仓/冷冻期同样是状态机 dp每天从几个状态互相转移最小路径和dp[i][j] 表示到达格子的最小花费转移来自上方和左方是一个二维的线性 dp编辑距离dp[i][j] 表示两个前缀匹配的花费一维顺序变成了两个序列的二维顺序你可以看到它们的底层都是“状态转移”。状态定义写得好不好直接决定转移方程顺不顺手。这也是为什么我特别强调刷题不能只背答案要多问“状态里为什么多一维”5.3 那些刷题群里常听到的 dp 热词和这道题什么关系刷题群里经常飘着“树形dp”“数位dp”“单调队列优化dp”这些热词。它们和粉刷房子其实是同一个世界观里的不同分支。粉刷房子的状态是“房子编号颜色”树形dp 的状态是“树上的节点编号该节点的状态选或不选、涂色或涂其他颜色”转移发生在父子节点之间比如“没有上司的舞会”就是树形dp 的入门题。数位dp 则是“数位位置是否贴着上界”在数字位上做递归记忆化。单调队列优化 dp 解决的是滑动窗口最值参与转移的问题和 4.3 节那个“最小值和次小值”的优化思路是一脉相承的想办法把转移中最耗时的部分预先算好。顺着这个脉络看动态规划真的不是一个题目而是一整套方法论。粉刷房子教给我们的“状态记录必要信息、转移排除非法情况、滚动数组压缩空间”放到任何一道 dp 题里都用得上。我的建议是如果你刚开始跟动规题单刷完粉刷房子后花二十分钟把这三个变体都想一遍颜色变成 k 种怎么改房子变成环形怎么改如果颜色多到 k 很大又要充分优化怎么改想完再动手写写一遍再对照最优代码。等这三关都过了你再回头看就会发现 dp 题的核心从来不是“记住这道题”而是“你能不能在陌生题里认出它和粉刷房子共享的骨架。”这个能力只能靠一题一题亲手写出来。

从粉刷房子看线性dp：状态设计与优化的完整拆解

相关推荐

OpenCV双目测距实战：BM算法从视差图到距离转换的避坑指南

Android ListView/RecyclerView吸顶实现原理与踩坑指南

受控Agent工作流设计：以退款场景为例的状态机与控制机制

更多资讯

UVa 12266 股票价格：用STL map模拟订单簿撮合

C# ONNX Runtime 部署 DAViD 软前景分割实战

对话式AI记忆系统设计：从存储选型到混合检索的工程实践

AI Agent 如何精准调用技能？从入门到精通的 6 步链路解析

有哪些CCF A类期刊对国内学者特别友好

存储行业进入利润兑现周期，AI 需求重塑 DRAM 与 HBM 产能格局

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？