线性动态规划：粉刷房子问题（Paint House） 题目描述 给定一排 n 座房子，每座房子可以用三种颜色之一（红色、蓝色或绿色）进行粉刷。粉刷第 i 座房子使用某种颜色的成本由 n x 3 的成本矩阵 costs 表示，其中 costs[i][0] 、 costs[i][1] 和 costs[i][2] 分别表示粉刷第 i 座房子为红色、蓝色和绿色的成本。要求：相邻的两座房子不能粉刷成相同的颜色。请计算粉刷所有房子的最小总成本。 示例 输入： costs = [[17,2,17],[16,16,5],[14,3,19]] 输出： 10 解释：第一座房子刷蓝色（成本2），第二座房子刷绿色（成本5），第三座房子刷蓝色（成本3），总成本为2 + 5 + 3 = 10。 解题过程 步骤1：定义状态 这是一个典型的序列型动态规划问题。我们需要按顺序处理每一座房子，并在粉刷时考虑颜色限制。定义状态： dp[i][0] 表示粉刷前 i 座房子，且第 i 座房子刷成红色的最小总成本。 dp[i][1] 表示粉刷前 i 座房子，且第 i 座房子刷成蓝色的最小总成本。 dp[i][2] 表示粉刷前 i 座房子，且第 i 座房子刷成绿色的最小总成本。 步骤2：状态转移方程 对于第 i 座房子（ i ≥ 1 ），其颜色不能与第 i-1 座房子相同： 如果第 i 座房子刷红色（ 0 ），则第 i-1 座房子只能是蓝色或绿色： dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0] 如果第 i 座房子刷蓝色（ 1 ），则第 i-1 座房子只能是红色或绿色： dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1] 如果第 i 座房子刷绿色（ 2 ），则第 i-1 座房子只能是红色或蓝色： dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2] 步骤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[i][0..2] 。 步骤5：最终答案 粉刷完所有 n 座房子的最小总成本为： min(dp[n-1][0], dp[n-1][1], dp[n-1][2]) 示例推导 以 costs = [[17,2,17],[16,16,5],[14,3,19]] 为例： 初始化： dp[0] = [17, 2, 17] 计算第二座房子（ i=1 ）： dp[1][0] = min(dp[0][1], dp[0][2]) + 16 = min(2,17) + 16 = 18 dp[1][1] = min(dp[0][0], dp[0][2]) + 16 = min(17,17) + 16 = 33 dp[1][2] = min(dp[0][0], dp[0][1]) + 5 = min(17,2) + 5 = 7 dp[1] = [18, 33, 7] 计算第三座房子（ i=2 ）： dp[2][0] = min(dp[1][1], dp[1][2]) + 14 = min(33,7) + 14 = 21 dp[2][1] = min(dp[1][0], dp[1][2]) + 3 = min(18,7) + 3 = 10 dp[2][2] = min(dp[1][0], dp[1][1]) + 19 = min(18,33) + 19 = 37 dp[2] = [21, 10, 37] 最终结果： min(21,10,37) = 10 复杂度分析 时间复杂度：O(n)，需要遍历每座房子一次。 空间复杂度：O(n)，可优化至 O(1) 仅保留前一座房子的状态。