好的，我们来学习一道经典的线性动态规划题目，它被称为 “打家劫舍” 的升级版，但约束条件更为复杂和现实。这道题是：
粉刷房子
题目描述：
你是一个专业的油漆匠，准备粉刷一排 n 座房子。每座房子都可以被粉刷成三种颜色之一：红色、蓝色或绿色。粉刷每座房子的成本因颜色不同而不同。给定一个 n x 3 的成本矩阵 costs，其中 costs[i][0]、costs[i][1] 和 costs[i][2] 分别表示粉刷第 i 座房子为红色、蓝色和绿色的成本。
你需要设计一个粉刷方案，使得相邻的两座房子不能粉刷成相同的颜色。
请你计算并返回粉刷所有房子所需的最小总成本。
解题过程
这道题的本质是一个“状态决策”问题。对于每一座房子，你的选择（状态）取决于前一座房子的颜色，以避免冲突。
步骤 1: 定义状态
我们需要一个数组来记录“粉刷到第 i 座房子，并且把它粉刷成特定颜色时，累计的最小成本”。
一个直观的定义是：
- 定义
dp[i][0]为：粉刷完前i座房子，并且第i座房子被粉刷成红色时的最小总成本。 - 定义
dp[i][1]为：粉刷完前i座房子，并且第i座房子被粉刷成蓝色时的最小总成本。 - 定义
dp[i][2]为：粉刷完前i座房子，并且第i座房子被粉刷成绿色时的最小总成本。
其中 i 从 0 开始（即第一座房子的下标为 0）。
步骤 2: 推导状态转移方程
关键在于：如果你要把第 i 座房子粉刷成红色 (dp[i][0])，那么第 i-1 座房子必须是蓝色或绿色。所以：
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])- 当前房子
i刷成红色的成本costs[i][0]，加上前一座房子刷成蓝色或绿色时的最小累计成本。
- 当前房子
同理：
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])
这个方程清晰地反映了“相邻房子颜色不同”的约束。
步骤 3: 确定初始条件
对于第一座房子 (i = 0)，没有“前一座房子”的限制，所以最小成本就是直接粉刷它的成本：
dp[0][0] = costs[0][0]dp[0][1] = costs[0][1]dp[0][2] = costs[0][2]
步骤 4: 确定计算顺序和最终答案
我们从 i = 1 开始，依次计算到 i = n-1（最后一座房子）。计算顺序是自然的从左到右（线性扫描）。
最终答案不是 dp[n-1] 的某一个值，而是三种颜色方案中的最小值，因为你只关心总成本最小，不关心最后一间房子是什么颜色：
answer = min(dp[n-1][0], dp[n-1][1], dp[n-1][2])
步骤 5: 举例说明
假设我们有 n = 3 座房子，成本矩阵如下：
costs = [[17, 2, 17],
[16, 16, 5],
[14, 3, 19]]
初始化：
dp[0] = [17, 2, 17](对应第一座房子刷成红、蓝、绿的成本)
计算 i = 1 (第二座房子)：
- 刷成红色：
dp[1][0] = costs[1][0] + min(dp[0][1], dp[0][2]) = 16 + min(2, 17) = 16 + 2 = 18 - 刷成蓝色：
dp[1][1] = costs[1][1] + min(dp[0][0], dp[0][2]) = 16 + min(17, 17) = 16 + 17 = 33 - 刷成绿色：
dp[1][2] = costs[1][2] + min(dp[0][0], dp[0][1]) = 5 + min(17, 2) = 5 + 2 = 7 - 此时
dp[1] = [18, 33, 7]
计算 i = 2 (第三座房子)：
- 刷成红色：
dp[2][0] = costs[2][0] + min(dp[1][1], dp[1][2]) = 14 + min(33, 7) = 14 + 7 = 21 - 刷成蓝色：
dp[2][1] = costs[2][1] + min(dp[1][0], dp[1][2]) = 3 + min(18, 7) = 3 + 7 = 10 - 刷成绿色：
dp[2][2] = costs[2][2] + min(dp[1][0], dp[1][1]) = 19 + min(18, 33) = 19 + 18 = 37 - 此时
dp[2] = [21, 10, 37]
最终答案：
min(21, 10, 37) = 10
所以，最小总成本是 10。可以回溯验证一个方案：第一座房子蓝色(2)，第二座房子绿色(5)，第三座房子蓝色(3)，总成本 2+5+3=10，且满足相邻颜色不同的约束。
步骤 6: 空间优化
注意到在计算 dp[i] 时，我们只依赖于 dp[i-1]。因此，我们不需要保存整个二维数组，只需要保存前一个状态即可。可以用三个变量 prev_red, prev_blue, prev_green 来记录 dp[i-1][0], dp[i-1][1], dp[i-1][2]，然后不断滚动更新。这样可以将空间复杂度从 O(n) 优化到 O(1)。
总结
这道 粉刷房子 问题是一个典型的线性动态规划问题，其核心在于：
- 识别状态：对每个位置（房子），定义多个状态（刷成不同颜色）。
- 建立转移：当前状态的成本由前一个位置的不同颜色状态的最小值加上当前成本决定。
- 处理约束：状态转移方程天然编码了“相邻不同色”的约束。
这个思路可以扩展到更多颜色（k 种）或更复杂的相邻约束（如隔一个房子颜色不能相同等），是学习线性动态规划中“多维状态”的一个绝佳范例。