企业官网建设流程全解析

如果你正在按动态规划题单刷题，大概率会在前二三十题的位置遇到“粉刷房子”。这道题的标签是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 个房子的全局最小花费”，因为全局最小花费这个信息，不足以支撑我们把第 i+1 个房子接上去。

第三，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[i+1][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 等于 1

LeetCode 的输入有时候会给你n = 0或者n = 1，这两种情况最容易忽略。

• n = 0：没有房子，总花费是 0，直接返回 0。
• n = 1：只有一间房子，没有任何相邻约束，选三种颜色里最便宜的那个就行，即min(cost[0])。

对应的代码在 3.1 节里已经覆盖了 n=0 的情况，dp[0]也能正确处理 n=1，但如果你是单独判断的人，要注意 dp 数组长度为 0 时不能去访问dp[0]，会直接越界报错。写完代码后，建议一定把这三种情况跑一遍：[[1,2,3]]（n=1）和[]（n=0），实测下来很多一眼对的代码在[]上都会崩。

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 几道和粉刷房子“长得像”的兄弟题

刷题有体系很重要，做完粉刷房子后可以立刻去做下面几道题，对比状态设计上的异同：

你可以看到，它们的底层都是“状态 + 转移”。状态定义写得好不好，直接决定转移方程顺不顺手。这也是为什么我特别强调：刷题不能只背答案，要多问“状态里为什么多一维？”

5.3 那些刷题群里常听到的 dp 热词，和这道题什么关系

刷题群里经常飘着“树形dp”“数位dp”“单调队列优化dp”这些热词。它们和粉刷房子其实是同一个世界观里的不同分支。粉刷房子的状态是“房子编号 + 颜色”，树形dp 的状态是“树上的节点编号 + 该节点的状态（选或不选、涂色或涂其他颜色）”，转移发生在父子节点之间，比如“没有上司的舞会”就是树形dp 的入门题。数位dp 则是“数位位置 + 是否贴着上界”，在数字位上做递归记忆化。单调队列优化 dp 解决的是滑动窗口最值参与转移的问题，和 4.3 节那个“最小值和次小值”的优化思路是一脉相承的：想办法把转移中最耗时的部分预先算好。

顺着这个脉络看，动态规划真的不是一个题目，而是一整套方法论。粉刷房子教给我们的“状态记录必要信息、转移排除非法情况、滚动数组压缩空间”，放到任何一道 dp 题里都用得上。

我的建议是，如果你刚开始跟动规题单，刷完粉刷房子后，花二十分钟把这三个变体都想一遍：颜色变成 k 种怎么改？房子变成环形怎么改？如果颜色多到 k 很大又要充分优化怎么改？想完再动手写，写一遍再对照最优代码。等这三关都过了，你再回头看就会发现 dp 题的核心从来不是“记住这道题”，而是“你能不能在陌生题里认出它和粉刷房子共享的骨架。”这个能力，只能靠一题一题亲手写出来。