如果你刷过一段时间的算法题多半遇到过这道经典动态规划题一排房子排排站每间房可以从红、蓝、绿三种颜色里挑一种刷相邻两间不能同色而每种颜色在不同房间的装修成本并不一样现在要你算整排房子最小的总花费。它在 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 间选了红色第 i1 间绿色和蓝色还可以选但红色就不能选。于是这一间怎么选会直接影响下一间“能选什么”和“要花多少钱”。这种问题在现实里到处都是门店排班时相邻时段不能安排同一个人电商广告位相邻位置不能放同一个商品系列无线网络里相邻信道不能互相干扰。它们都能抽象成“在一长条位置上从有限选项里选一个相邻位置互相排斥总体代价最小”。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] 算好后续第 i1 间只关心“第 i 间是什么颜色、花费是多少”完全不关心更早的房子是怎么组合出来的。因为约束只发生在相邻两间历史细节对未来的影响已经全部浓缩在 dp[i][j] 这一个值里。这就是“记住影响未来的信息”这个 DP 思想的具象化。3. 核心拆解状态定义、转移方程与初始化3.1 状态定义为什么必须带上“最后一个颜色”先看一个错误示范定义 dp[i] 表示前 i 间房子的最小总花费。这样定义看似简洁但实际无法转移。原因很简单当我们要计算第 i1 间房子时需要知道第 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]。房子 idp[i][0] 红dp[i][1] 蓝dp[i][2] 绿0172171183372211037最后一行的计算也列一下第 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 代码时见过的问题汇总成一张表写题前先扫一眼能省不少调试时间。坑典型错误正确做法空数组直接访问 costs[0]先 if not costs: return 0初始化dp[0] 0dp[0] costs[0] 三种颜色分别记录Python 引用dp [[0]*3] * n用推导式 [[0]*3 for _ in range(n)]转移漏排除dp[i][j] costs[i][j] min(dp[i-1])必须排除 k j返回值return min(costs[-1])return min(dp[-1])即经过 DP 累加后的最小值滚动顺序先覆盖 prev 再算下一个 cur当前行统一算完再整体更新单房边界n1 时循环不执行返回随机初值把 prev 初始化为 costs[0]无穷大使用把 dp 初始值写成 0导致中途吞掉正数用 float(inf) 或确定性初始化其中“转移漏排除”最隐蔽。比如在 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 就再也不会是你面试路上的拦路虎了。