线性动态规划：粉刷房子

字数 2523 2025-10-29 21:04:18

线性动态规划：粉刷房子

题目描述
你是一个专业的油漆工，需要粉刷一排房子。每个房子可以用三种颜色中的一种来粉刷：红色、蓝色或绿色。粉刷每个房子用不同颜色的成本是不同的。给定一个 n x 3 的成本矩阵 costs，其中 costs[i][0]、costs[i][1] 和 costs[i][2] 分别表示粉刷第 i 个房子用红色、蓝色和绿色的成本。

你需要设计一个算法来计算粉刷完所有房子的最小总成本。但是，有一个重要的限制：相邻的两个房子不能粉刷成相同的颜色。

解题过程

问题分析
这是一个典型的序列型动态规划问题。我们需要为一系列房子（一个序列）做出决策（选择颜色），每个决策会影响后续的决策（因为相邻房子颜色不能相同）。我们的目标是找到一组决策，使得总成本最小。
定义状态
我们定义动态规划数组 dp[i][j]，它表示的含义是：粉刷前 i 个房子，并且第 i 个房子被粉刷成颜色 j 时的最小总成本。
通常，我们用 j = 0 代表红色，j = 1 代表蓝色，j = 2 代表绿色。
状态转移方程
这是整个问题的核心。我们如何由已知的前 i-1 个房子的状态，推导出前 i 个房子的状态？
- 考虑第 i 个房子被粉刷成了颜色 j（例如红色）。
- 那么，第 i-1 个房子就不能是颜色 j。它只能是另外两种颜色（蓝色或绿色）中的一种。
- 因此，粉刷前 i 个房子且第 i 个是颜色 j 的最小成本，应该等于：
  - 粉刷前 i-1 个房子且第 i-1 个是颜色 k (k ≠ j) 的最小成本
  - 加上 粉刷第 i 个房子为颜色 j 的成本 costs[i-1][j]。
  - 然后我们在所有可能的 k (k ≠ j) 中，取这个和的最小值。
用数学公式表达状态转移方程：
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2]

注意：由于编程中数组索引从0开始，costs[i-1] 对应的是第 i 个房子的成本。
初始化
我们考虑粉刷前0个房子的情况，即 i = 0。
- dp[0][0]：粉刷前0个房子，且第0个（不存在）是红色。这没有成本，所以初始化为0。
- 同理，dp[0][1] 和 dp[0][2] 也都初始化为0。
计算顺序
由于 dp[i] 的状态只依赖于 dp[i-1]，我们可以从 i = 1 开始，一直计算到 i = n。
最终答案
当我们计算完 dp[n][0], dp[n][1], dp[n][2] 后，它们分别表示粉刷完所有 n 个房子，并且最后一个房子是红色、蓝色或绿色时的最小成本。由于题目只要求总成本最小，不限制最后一个房子的颜色，所以我们的最终答案就是这三个值中的最小值：min(dp[n][0], dp[n][1], dp[n][2])。
示例演示
假设成本矩阵 costs 为：[[17, 2, 17], [16, 5, 13], [14, 3, 19]]，表示有3个房子。
- 初始化：dp[0] = [0, 0, 0]
- 计算 i=1 (第一个房子)：
  - dp[1][0] = min(dp[0][1], dp[0][2]) + costs[0][0] = min(0, 0) + 17 = 17
  - dp[1][1] = min(dp[0][0], dp[0][2]) + costs[0][1] = min(0, 0) + 2 = 2
  - dp[1][2] = min(dp[0][0], dp[0][1]) + costs[0][2] = min(0, 0) + 17 = 17
  - 此时 dp[1] = [17, 2, 17]
- 计算 i=2 (第二个房子)：
  - dp[2][0] = min(dp[1][1], dp[1][2]) + costs[1][0] = min(2, 17) + 16 = 2 + 16 = 18
  - dp[2][1] = min(dp[1][0], dp[1][2]) + costs[1][1] = min(17, 17) + 5 = 17 + 5 = 22
  - dp[2][2] = min(dp[1][0], dp[1][1]) + costs[1][2] = min(17, 2) + 13 = 2 + 13 = 15
  - 此时 dp[2] = [18, 22, 15]
- 计算 i=3 (第三个房子)：
  - dp[3][0] = min(dp[2][1], dp[2][2]) + costs[2][0] = min(22, 15) + 14 = 15 + 14 = 29
  - dp[3][1] = min(dp[2][0], dp[2][2]) + costs[2][1] = min(18, 15) + 3 = 15 + 3 = 18
  - dp[3][2] = min(dp[2][0], dp[2][1]) + costs[2][2] = min(18, 22) + 19 = 18 + 19 = 37
  - 此时 dp[3] = [29, 18, 37]
- 最终答案：min(29, 18, 37) = 10
  这个最小成本方案是：第一个房子刷蓝色(成本2)，第二个房子刷绿色(成本13)，第三个房子刷蓝色(成本3)。总成本 2 + 13 + 3 = 18。符合相邻房子颜色不同的规则。
空间优化
观察状态转移方程，计算 dp[i] 时只用到 dp[i-1]，而与更早的状态无关。因此，我们可以不使用长度为 n+1 的数组，而只用两个变量（或一个长度为3的数组）来滚动存储状态，将空间复杂度从 O(n) 优化到 O(1)。

线性动态规划：粉刷房子题目描述你是一个专业的油漆工，需要粉刷一排房子。每个房子可以用三种颜色中的一种来粉刷：红色、蓝色或绿色。粉刷每个房子用不同颜色的成本是不同的。给定一个 n x 3 的成本矩阵 costs ，其中 costs[i][0] 、 costs[i][1] 和 costs[i][2] 分别表示粉刷第 i 个房子用红色、蓝色和绿色的成本。你需要设计一个算法来计算粉刷完所有房子的最小总成本。但是，有一个重要的限制：相邻的两个房子不能粉刷成相同的颜色。解题过程问题分析这是一个典型的序列型动态规划问题。我们需要为一系列房子（一个序列）做出决策（选择颜色），每个决策会影响后续的决策（因为相邻房子颜色不能相同）。我们的目标是找到一组决策，使得总成本最小。定义状态我们定义动态规划数组 dp[i][j] ，它表示的含义是：粉刷前 i 个房子，并且第 i 个房子被粉刷成颜色 j 时的最小总成本。通常，我们用 j = 0 代表红色， j = 1 代表蓝色， j = 2 代表绿色。状态转移方程这是整个问题的核心。我们如何由已知的前 i-1 个房子的状态，推导出前 i 个房子的状态？考虑第 i 个房子被粉刷成了颜色 j （例如红色）。那么，第 i-1 个房子就不能是颜色 j 。它只能是另外两种颜色（蓝色或绿色）中的一种。因此，粉刷前 i 个房子且第 i 个是颜色 j 的最小成本，应该等于：粉刷前 i-1 个房子且第 i-1 个是颜色 k (k ≠ j) 的最小成本加上粉刷第 i 个房子为颜色 j 的成本 costs[i-1][j] 。然后我们在所有可能的 k (k ≠ j) 中，取这个和的最小值。用数学公式表达状态转移方程： dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1] dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2] 注意：由于编程中数组索引从0开始， costs[i-1] 对应的是第 i 个房子的成本。初始化我们考虑粉刷前0个房子的情况，即 i = 0 。 dp[0][0] ：粉刷前0个房子，且第0个（不存在）是红色。这没有成本，所以初始化为0。同理， dp[0][1] 和 dp[0][2] 也都初始化为0。计算顺序由于 dp[i] 的状态只依赖于 dp[i-1] ，我们可以从 i = 1 开始，一直计算到 i = n 。最终答案当我们计算完 dp[n][0] , dp[n][1] , dp[n][2] 后，它们分别表示粉刷完所有 n 个房子，并且最后一个房子是红色、蓝色或绿色时的最小成本。由于题目只要求总成本最小，不限制最后一个房子的颜色，所以我们的最终答案就是这三个值中的最小值： min(dp[n][0], dp[n][1], dp[n][2]) 。示例演示假设成本矩阵 costs 为： [[17, 2, 17], [16, 5, 13], [14, 3, 19]] ，表示有3个房子。初始化： dp[0] = [0, 0, 0] 计算 i=1 (第一个房子) ： dp[1][0] = min(dp[0][1], dp[0][2]) + costs[0][0] = min(0, 0) + 17 = 17 dp[1][1] = min(dp[0][0], dp[0][2]) + costs[0][1] = min(0, 0) + 2 = 2 dp[1][2] = min(dp[0][0], dp[0][1]) + costs[0][2] = min(0, 0) + 17 = 17 此时 dp[1] = [17, 2, 17] 计算 i=2 (第二个房子) ： dp[2][0] = min(dp[1][1], dp[1][2]) + costs[1][0] = min(2, 17) + 16 = 2 + 16 = 18 dp[2][1] = min(dp[1][0], dp[1][2]) + costs[1][1] = min(17, 17) + 5 = 17 + 5 = 22 dp[2][2] = min(dp[1][0], dp[1][1]) + costs[1][2] = min(17, 2) + 13 = 2 + 13 = 15 此时 dp[2] = [18, 22, 15] 计算 i=3 (第三个房子) ： dp[3][0] = min(dp[2][1], dp[2][2]) + costs[2][0] = min(22, 15) + 14 = 15 + 14 = 29 dp[3][1] = min(dp[2][0], dp[2][2]) + costs[2][1] = min(18, 15) + 3 = 15 + 3 = 18 dp[3][2] = min(dp[2][0], dp[2][1]) + costs[2][2] = min(18, 22) + 19 = 18 + 19 = 37 此时 dp[3] = [29, 18, 37] 最终答案： min(29, 18, 37) = 10 这个最小成本方案是：第一个房子刷蓝色(成本2)，第二个房子刷绿色(成本13)，第三个房子刷蓝色(成本3)。总成本 2 + 13 + 3 = 18。符合相邻房子颜色不同的规则。空间优化观察状态转移方程，计算 dp[i] 时只用到 dp[i-1] ，而与更早的状态无关。因此，我们可以不使用长度为 n+1 的数组，而只用两个变量（或一个长度为3的数组）来滚动存储状态，将空间复杂度从 O(n) 优化到 O(1)。