线性动态规划：粉刷房子问题（Paint House）

题目描述
假设有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或绿色中的任意一种颜色。粉刷每个房子时，需要根据其颜色产生不同的成本。给定一个 n x 3 的成本矩阵 costs，其中 costs[i][0]、costs[i][1] 和 costs[i][2] 分别表示粉刷第 i 个房子为红色、蓝色和绿色的成本。要求相邻的两个房子不能粉刷成相同的颜色。请计算粉刷完所有房子所需的最小总成本。

解题过程

1. 问题分析

   • 目标：最小化总成本，同时满足相邻房子颜色不同的约束。
   • 每个房子的颜色选择会影响后续房子的选择，具有重叠子问题和最优子结构性质，适合用动态规划求解。

2. 定义状态

   • 设 dp[i][j] 表示粉刷前 i 个房子，且第 i 个房子颜色为 j（j 取 0、1、2，分别代表红、蓝、绿）时的最小总成本。

3. 状态转移方程

   • 对于第 i 个房子颜色为 j，前一个房子（第 i-1 个）的颜色不能为 j，只能从另外两种颜色中选择。
   • 转移方程：

     dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]  // 第i个房子涂红色
     dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]  // 第i个房子涂蓝色
     dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]  // 第i个房子涂绿色
     

4. 初始化

   • 第一个房子的成本直接由 costs[0] 初始化：

     dp[0][0] = costs[0][0]
     dp[0][1] = costs[0][1]
     dp[0][2] = costs[0][2]
     

5. 计算顺序

   • 按房子编号 i 从 1 到 n-1 顺序计算，确保计算 dp[i] 时 dp[i-1] 已确定。

6. 结果提取

   • 最小总成本为 min(dp[n-1][0], dp[n-1][1], dp[n-1][2])。

7. 示例演示
   假设 costs = [[17, 2, 17], [16, 5, 13], [10, 1, 15]]：

   • 初始化：dp[0] = [17, 2, 17]
   • i=1（第二个房子）：
     • 涂红色：min(2, 17) + 16 = 2 + 16 = 18
     • 涂蓝色：min(17, 17) + 5 = 17 + 5 = 22
     • 涂绿色：min(17, 2) + 13 = 2 + 13 = 15
     • dp[1] = [18, 22, 15]
   • i=2（第三个房子）：
     • 涂红色：min(22, 15) + 10 = 15 + 10 = 25
     • 涂蓝色：min(18, 15) + 1 = 15 + 1 = 16
     • 涂绿色：min(18, 22) + 15 = 18 + 15 = 33
     • dp[2] = [25, 16, 33]
   • 最终结果：min(25, 16, 33) = 16

8. 优化

   • 由于 dp[i] 仅依赖 dp[i-1]，可用三个变量滚动更新，将空间复杂度从 O(n) 降至 O(1)。

总结
通过定义状态表示当前房子的颜色选择，并利用约束条件递推，逐步得到全局最优解。此方法可扩展至更多颜色或相邻约束更复杂的情况。