企业官网建设流程全解析

如果你刷过一段时间的算法题，多半遇到过这道经典动态规划题：一排房子排排站，每间房可以从红、蓝、绿三种颜色里挑一种刷，相邻两间不能同色，而每种颜色在不同房间的装修成本并不一样，现在要你算整排房子最小的总花费。它在 LeetCode 上的名字就是 Paint House，也被无数入门题单收进“动态规划”专栏。我第一次看到题目时心想：刷个房子而已，也配叫动态规划？直到自己写了个暴力递归被 OJ 超时，才不得不正视这题背后真正的考察点。它不是考你会不会涂色，而是考你能不能把一个连续决策问题拆成“阶段 + 状态 + 转移”的模型。这篇文章适合刚接触动态规划的人当第一道自测题，也适合准备算法面试的同学用来梳理线性 DP 的通用套路。

1. 先看题：Paint House 到底在解决什么问题？

1.1 原题长什么样，边界条件有哪些

题目描述很直白：有 n 栋房子排成一排，每栋房子可以被粉刷成红、蓝、绿三种颜色中的任意一种，相邻的房子不能粉刷成相同的颜色。给定一个 n x 3 的成本矩阵 costs，其中 costs[i][0]、costs[i][1]、costs[i][2] 分别代表第 i 栋房子刷红、蓝、绿三种颜色的花费，要求计算整排房子的最低总花费。注意“花费”可以是任意非负整数，没有说一定递增或递减，所以不能指望排序取巧。

这里有个边界容易被忽略：n 可以是 0，此时没有房子，花费自然是 0。n 等于 1 时，没有相邻约束，答案就是 costs[0] 中三种颜色的最小值。这两种情况在写代码时要单独处理，不然要么空数组越界，要么循环里没有跑任何东西导致返回错误。

为了后面讲状态转移方便，我们先固定一个标准示例。假设输入 costs = [[17,2,17],[16,16,5],[14,3,19]]。最直观的最优解是：第一间刷蓝色花 2，第二间刷绿色花 5，第三间刷蓝色花 3，总花费 10。这里第一间和第三间都是蓝色，但因为不相邻，并不违反规则。这个反直觉点值得记下来：同色限制的只是相邻关系，不是所有位置。

1.2 为什么“相邻不同色”是核心约束

如果没有相邻不同色这条，问题就退化成了每个房间独立选择最低价颜色，直接对每行取 min 再求和，十秒钟做完。真正让题目变难的是那条互斥约束：你在第 i 间选了红色，第 i+1 间绿色和蓝色还可以选，但红色就不能选。于是这一间怎么选，会直接影响下一间“能选什么”和“要花多少钱”。

这种问题在现实里到处都是：门店排班时相邻时段不能安排同一个人，电商广告位相邻位置不能放同一个商品系列，无线网络里相邻信道不能互相干扰。它们都能抽象成“在一长条位置上，从有限选项里选一个，相邻位置互相排斥，总体代价最小”。Paint House 就是把这种抽象做到最简的一题，所以它才有资格成为线性 DP 的入门代表。理解这一点，再看后面所有推导都会觉得顺。

1.3 暴力枚举为什么撑不住

初学者最容易想到的是暴力深搜：从第一间开始，枚举三种颜色；第二间在排除上一间颜色的前提下枚举；第三间继续。整个过程形成一棵搜索树，理论上最大分支数是 2，但由于第一间有 3 个分支，总方案数是 3 * 2^(n-1)，也就是指数级。当 n 只有 20 时，方案数已经接近 50 万；n 到 40 就是几千万；n 到 100 时，任何普通计算机都不可能跑完。所以问题不在于“会不会算”，而在于“能不能把已经算过的结果保存下来复用”。这正是动态规划模型原理要解决的事。

2. 为什么第一反应“贪心”会翻车：从错误思路到动态规划

2.1 一个看似合理的做法：每间都挑当前最便宜的

很多人在不熟悉 DP 时，会提出一个很自然的贪心方案：从左到右扫一遍，第一间选最便宜的颜色；后面的每一间都选“当前这间最便宜且不与前一间同色”的颜色。这听起来很符合直觉，也确实在很多简单例子上能跑出正确答案，但它不是总能成立的。我构造一个极端例子：costs = [[1,100,100],[2,100,100],[100,1,100]]。

逐间贪心是这样的：第一间红色最便宜，1 元；第二间不能红色，蓝色和绿色都是 100，随便选一个，比如蓝色 100；第三间不能蓝色，红色和绿色都是 100，选红色 100，总花费 201。但如果你把第一间涂绿色（100），第二间涂红色（2），第三间涂蓝色（1），总花费只有 103。差接近一倍。这个反例不是故意凑出来的，它很典型：早期省下的 99 元，会在后面变成必须多付的 100 元。

2.2 贪心到底贪丢了什么

贪心的本质是“每次做局部最优，并假设局部最优能拼成全局最优”。但 Paint House 里，选择会影响未来可选集合，局部最优和全局最优之间没有保证关系。第一间省下的钱，可能剥夺了第二间低成本颜色可用性，然后层层传导到后面。它不像找零钱问题里硬币可以重复使用，选择之间相互独立；这里的决策是强耦合的，每一步都会给后续留下“限制”。

更深一层看，贪心没有记忆。它只记住了“上一间颜色”，却不知道“在不同的上一间颜色下，前 i 间的累计花费分别是什么”。比如第二间选了蓝色，花费 100，这看起来是一个状态；但如果第一间涂绿色而不是红色，第二间还是可以涂红色，并且总花费可能更少。贪心没有比较这些不同路径，只是锁死一条路线。要表达这些可能路径，需要一个能同时记录“当前颜色”和“当前花费”的数据结构，这就自然走到 DP 的状态定义了。

2.3 动态规划模型的核心：用阶段和状态对抗维度爆炸

动态规划处理这类问题有一套固定套路。第一步划分阶段：把“前 i 间房子已经刷完”作为第 i 个阶段，i 从 0 一直推进到 n-1。第二步定义状态：dp[i][j] 表示“第 i 间房子刷颜色 j，并且前 i 间房子总花费最小”时的最小值。第三步确定决策：第 i 间刷哪个颜色。第四步写出转移：把第 i 间的花费和前面最优子结构拼接起来。这四个词听起来抽象，但放在 Paint House 里非常具体。阶段是房子的顺序，状态是最后一个颜色，决策是选颜色，转移就是 min 操作。这也解释了为什么它被叫线性 DP：阶段是一条直线往前推，状态的依赖只来自前一个阶段，不存在回头跳转。

这里还要强调一个关键性质——无后效性。一旦 dp[i][j] 算好，后续第 i+1 间只关心“第 i 间是什么颜色、花费是多少”，完全不关心更早的房子是怎么组合出来的。因为约束只发生在相邻两间，历史细节对未来的影响已经全部浓缩在 dp[i][j] 这一个值里。这就是“记住影响未来的信息”这个 DP 思想的具象化。

3. 核心拆解：状态定义、转移方程与初始化

3.1 状态定义：为什么必须带上“最后一个颜色”

先看一个错误示范：定义 dp[i] 表示前 i 间房子的最小总花费。这样定义看似简洁，但实际无法转移。原因很简单：当我们要计算第 i+1 间房子时，需要知道第 i 间房子是什么颜色，才能判断两种颜色哪些被禁止。而 dp[i] 只是一个数字，它丢掉了颜色信息。你只知道“前 3 间房最少花了 14 块”，但不知道第 3 间是红是蓝，怎么知道第 4 间能不能涂红？

所以状态必须包含“能影响未来决策的所有信息”。在这个问题里，唯一影响下一间选择的就是当前颜色，于是状态写成 dp[i][0]，dp[i][1]，dp[i][2] 分别表示第 i 间刷三种颜色时前 i 间的最小总花费。这个思想在动态规划里极其重要：股票买卖问题里状态要带“是否持有股票”，背包问题里状态要带“还剩多少容量”，本质都是同一个道理。多一个维度不是炫技，是为了把决策所需的记忆留下。

3.2 转移方程：从上一间房“滚”过来

状态定义清楚后，转移几乎是顺理成章的。若第 i 间刷颜色 j，那么上一间一定不能刷颜色 j，只能刷另外两种颜色中的一种。为了总花费最小，我们就在上一间那两个合法颜色中取最小值。于是转移方程写为：

dp[i][j] = costs[i][j] + min(dp[i-1][k])，其中 k 遍历 0、1、2 且 k != j。

初始化也很直接：第 0 间没有任何前驱，所以 dp[0][j] = costs[0][j]，三种颜色分别记下花费。最终答案是 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])，因为最后一段总花费由三种颜色中最小者决定，而不是从 costs 的最后一行里直接取 min。很多初学者在这里会犯糊涂：为什么最后还要 min？因为 dp[n-1][j] 代表“第 n-1 间刷 j 颜色时前 n 间的最小总花费”，三种颜色都是合法终点，自然要选最小者。

这个转移方程里出现了一个“排除自己”的细节：当上一间颜色是 j 时，不能参与 min。写成代码时容易漏掉，尤其是后面用通用写法时，一个 min(dp[i-1]) 会把同色状态也算进来，结果偏小。

3.3 代码实现：一个可以直接跑的版本

我用 Python 写一个最直观的版本，二维数组存状态，便于新手对照方程：

def minCost(costs): if not costs: return 0 n = len(costs) dp = [[0, 0, 0] for _ in range(n)] dp[0] = costs[0][:] # 初始化第一间 for i in range(1, n): dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) return min(dp[-1])

需要留意的是 dp[0] = costs[0][:] 这行。如果图省事写成 dp[0] = costs[0]，在 Python 里会让 dp[0] 和 costs[0] 指向同一个列表对象，后续修改直接影响原矩阵。虽然在这个具体函数里不影响最终结果，但在更复杂的场景会出诡异 bug，所以用切片复制一份是稳妥习惯。另一个容易忽略的是空输入判断，刷题平台的测试用例里一定有 n = 0 的情况。

3.4 手推一张二维 DP 表：从数字看状态生长

光看方程不够，我建议你亲手推一遍表。还是用前面的示例 costs = [[17,2,17],[16,16,5],[14,3,19]]。初始化第 0 行，也就是第 0 间房子分别刷红、蓝、绿的花费：红色 17，蓝色 2，绿色 17。注意这里不是“选了最优”，而是三种可能性都保留。

接着算第 1 行。第 1 间刷红色时，上一间不能红色，所以取第 0 行蓝色 2 和绿色 17 中的较小值 2，加上本间红色 16，得到 18。刷蓝色时，上一间不能蓝色，取第 0 行红色 17 和绿色 17 中的较小值 17，加上本间蓝色 16，得到 33。刷绿色时，上一间不能绿色，取第 0 行红色 17 和蓝色 2 中的较小值 2，加上本间绿色 5，得到 7。于是第 1 行是 [18, 33, 7]。

最后一行的计算也列一下：第 2 间刷红色时，上一间取第 1 行蓝色 33、绿色 7 中的较小值 7，加本间红色 14，得 21。刷蓝色时，上一间取第 1 行红色 18、绿色 7 中的较小值 7，加本间蓝色 3，得 10。刷绿色时，上一间取第 1 行红色 18、蓝色 33 中的较小值 18，加本间绿色 19，得 37。最终取第 2 行的最小值 10，恰好等于肉眼观察的最优方案。整个过程中，dp 表保留的不只是最优路线，而是每一种合法末尾颜色的最优值，这就是它与贪心最大的不同。

4. 从典型代码到工程优化：空间压缩与变体扩展

4.1 空间压缩：滚动数组把二维变一维

写代码时你会发现，算第 i 行只用到了第 i-1 行，第 i-2 行及更早的完全用不上。因此不必开 n x 3 的二维数组，用一组变量滚动更新即可。这也是线性 DP 最常见的优化：把空间复杂度从 O(n) 降到 O(1)。

def minCost(costs): if not costs: return 0 prev0, prev1, prev2 = costs[0] for i in range(1, len(costs)): cur0 = costs[i][0] + min(prev1, prev2) cur1 = costs[i][1] + min(prev0, prev2) cur2 = costs[i][2] + min(prev0, prev1) prev0, prev1, prev2 = cur0, cur1, cur2 return min(prev0, prev1, prev2)

这段代码在面试里很常见，因为它既保留了 DP 思想，又展示了优化意识。但有一个非常容易翻车的点：更新顺序。如果你写 next0 = ... 后立刻覆盖 prev0，再用这个新 prev0 去计算 next1，就会把整行状态污染。我自己的做法是先进三个 cur 变量，算完再统一交给 prev，这样既清晰又安全。另一个小细节是循环结束后 prev0、prev1、prev2 分别代表最后一间房三种颜色下的最优值，所以返回值仍然是 min(prev0, prev1, prev2)。

4.2 颜色从 3 变成 K 之后：Paint House II 的经典优化

力扣的 follow-up 会把颜色数从 3 改成 K。此时状态变成 dp[i][0...K-1]，转移时要排除上一行第 j 个颜色，朴素写法需要枚举上一行所有颜色求 min，复杂度变成 O(nK^2)。K 一大就会很慢。优化的关键是：无论当前要算哪个 j，其实只是想快速知道“上一行除了某个位置以外的最小值”。可以提前扫描上一行，记下最小值和次小值，以及最小值所在颜色索引。

如果当前颜色 j 恰好是最小值所在颜色，那么只能取次小值；否则直接取最小值。这样每次转移都是 O(1)，总复杂度 O(nK)。这个“最小值和次小值”技巧不是 Paint House II 独占，很多带限制的状态 DP 都会用到。我在刷 hot100 动态规划专题时，就发现有题目把这种思路藏在更复杂的后处理里。记住它，你会比直接背代码的人更能应对变形。

4.3 扩展：环型房子、01 背包与更多“DP 亲戚”

如果把一排房子改成首尾相接的环，规则变成“第一间和最后一间也不能同色”，问题立刻又难了一档。常见解法是枚举第一间的颜色为 0、1、2，各跑一遍普通 Paint House 的 DP，但在初始化时强制第一间只能涂枚举的颜色，最后再检查最后一间的颜色不能等于枚举颜色，取所有合法情况里的最小值。这也是“用状态来编码额外约束”的典型应用。

另外，Paint House 经常被拿来和 01 背包问题动态规划对比。两者都是动态规划的基础模型，但结构不同：01 背包的状态是“物品下标 + 剩余容量”，决策是“选或不选”；Paint House 的状态是“房子下标 + 当前颜色”，决策是“三选一”。它们让你看到同一个套路可以有完全不同的状态维度。洛谷动态规划题单里通常先放数字三角形、最长上升子序列，再放背包，最后才是这类排列型 DP。你把 Paint House 吃透，再去看题单里的相邻约束题，会有一种“原来都是一个祖宗”的恍然大悟。至于实际工程里的车辆动态规划问题，本质上也无非是把时间、路段这些阶段变量和位置、速度这些状态变量塞进同一个 DP 框架，模型相通。

4.4 这题放在题单里应该怎么刷

我的建议是不要只盯着这题的答案。拿到题目先自己定义状态，写一遍二重循环；然后优化成滚动数组；再看 K 种颜色的变体；最后可以把环型版本当成扩展练习。如果你在准备面试，刷完这题后可以顺手把“打家劫舍”也重新做一遍，体会一下“状态只有 0/1 两个维度”和“状态有三个颜色维度”之间的关系。很多题单把 Paint House 放在线性 DP 开头，是因为它难度适中，又能展示 DP 的关键步骤，刷一道胜过机械刷十道。

5. 刷题与面试中的常见错误自查清单

5.1 八个容易踩的坑

我把实际刷题和帮别人 review 代码时见过的问题汇总成一张表，写题前先扫一眼能省不少调试时间。

其中“转移漏排除”最隐蔽。比如在 Paint House II 里，如果你直接写 best = min(prev) 而没看索引，颜色 j 本身也被算进候选，最终答案是偏小的。这种 bug 不会让你崩溃，只会悄悄给出一个离谱的正确答案，特别难发现。写出转移方程后，先手动跑一行，确认每个 j 都避开了同色约束，再写循环。

5.2 面试中这样讲，思路比背代码重要

面试官看这道题，不是真的在乎你会不会涂三间房子，而是想看你的思维能不能从暴力收敛到 DP。我建议按这个顺序讲：先说“直接暴力枚举是 3 * 2^(n-1)，指数级爆炸”；然后主动提起“贪心看起来可行，但有反例”，如果面试官有兴致，可以现场构造一个两行反例；接着定义状态 dp[i][j] 和前 i 间最小花费；再写出转移方程，强调排除同色；最后无后效性一句话收尾。这一套讲下来，比直接默写代码更能拿分。

有个话术你可以记住：“我之所以把颜色放进状态，是因为下一间房的合法颜色完全由当前颜色决定；我只需要记住当前最优值和当前颜色，不需要回顾更早的决策。”这句话简洁地点出了 DP 最核心的压缩思想。面试时边说边在纸上画矩阵，通常能引导面试官顺着你的思路走。

5.3 我的一个独家小技巧：顺手把状态表画出来

我自己刚开始学 DP 时最常犯的毛病是：代码跑通了，但被追问“这个 21 是怎么来的”就语塞。后来我养成了一个习惯：无论多简单的 DP 题，都在草稿纸上先画状态表，哪怕只有三行三列，也要把每个格子的产生过程写一遍。调试的时候也顺手 print 一下 dp 表，肉眼盯着状态怎么从左往右长出来。这个方法帮我改掉了不少“结果对但逻辑糊涂”的老毛病。

有一次做 Paint House II，我打印了上一行的最小值和次小值，发现某个中间状态下最小值索引是 1，而我在转移时忘了判断 j == 1，结果整行都取错。要不是把状态表打出来，这种问题靠肉眼看代码很难发现。这个习惯后来迁移到所有线性 DP 题上，基本都能较快定位问题。希望你在刷这题时也别急着背代码，先耐心把那条 2x3 或 3x3 的表填完，填通之后，Paint House 就再也不会是你面试路上的拦路虎了。