最多相邻k个房屋可粉刷同一颜色的粉刷房子 III（Paint House III）进阶问题

题目描述

你有一个由 n 栋房子排成一行的街道，每个房子可以被粉刷成 m 种颜色之一（标记为 1 到 m）。有些房子在粉刷前就已经被涂过颜色，用 houses[i] 表示（0 表示未粉刷，1..m 表示已粉刷的颜色）。你还有一个成本矩阵 cost[i][j]，表示将房子 i 粉刷成颜色 j+1 的代价。

你需要将所有房子涂上颜色，并满足以下条件：

1. 如果房子已预先有颜色，则必须保留该颜色（不能更改）。
2. 街道被分为若干“街区”（neighborhood），定义为一个连续的颜色相同的房子段。
3. 最终街区的总数必须恰好为 target。

问：在所有满足条件的粉刷方案中，最小总成本是多少？如果无法实现恰好 target 个街区，返回 -1。

示例
输入：

houses = [0,0,0,0,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
m = 2
target = 3

输出：9
解释：一种方案是 [1,2,1,2,1]（颜色编号从1开始），成本 = 1 + 1 + 1 + 1 + 5 = 9，街区分别是 [1]、[2]、[1]、[2]、[1] 共 3 个街区。

解题思路

这是一个经典的“粉刷房子 III”问题，结合了颜色选择、成本、街区数限制三种约束，是线性动态规划的典型题目。

我们可以定义状态为：

• dp[i][j][k] = 将前 i 个房子粉刷完，且第 i 个房子的颜色为 j，并形成了 k 个街区时的最小成本。

状态转移考虑第 i 个房子与第 i-1 个房子的颜色是否相同：

1. 如果 color[i] == color[i-1]，则街区数不变。
2. 如果 color[i] != color[i-1]，则街区数增加 1。

初始化：

• 第一个房子特殊处理，如果已涂色，则只有一种颜色可选，否则可涂任意颜色。
• 初始成本为 0 或对应涂色成本。

转移方程（详细推导见下）。

详细解题步骤

步骤 1：定义状态

设 dp[i][j][k] 表示：

• i 从 0 到 n-1（房子编号）
• j 从 0 到 m-1（颜色编号，实际颜色是 j+1）
• k 从 1 到 target（街区数，最少 1 个）

值：最小成本。如果不可行，用 INF 表示。

步骤 2：初始化

当 i = 0（第一个房子）时：

• 如果 houses[0] != 0（已涂色），设颜色为 c = houses[0]-1，则 dp[0][c][1] = 0（已涂色，无需新成本）。
• 如果 houses[0] == 0（未涂色），对每种颜色 j，dp[0][j][1] = cost[0][j]。
• 其余状态设为 INF。

注意：第一个房子无论涂什么颜色，街区数都是 1。

步骤 3：状态转移

对于 i ≥ 1：

• 枚举当前房子颜色 j（0 ≤ j < m），必须满足：如果 houses[i] 已涂色且不等于 j+1，则不可行，跳过。
• 枚举上一个房子颜色 p（0 ≤ p < m）。
• 枚举上一个房子的街区数 t（1 ≤ t ≤ target）。
• 如果 dp[i-1][p][t] 是 INF，跳过。
• 计算新街区数：new_k = t + (j == p ? 0 : 1)。
• 如果 new_k > target 跳过。
• 计算新成本：new_cost = dp[i-1][p][t] + (houses[i] == 0 ? cost[i][j] : 0)。
• 更新 dp[i][j][new_k] = min(dp[i][j][new_k], new_cost)。

步骤 4：答案

遍历最后一个房子 i = n-1 的所有颜色 j，取 dp[n-1][j][target] 的最小值。如果都是 INF，返回 -1，否则返回最小值。

时间复杂度与空间优化

• 原始：O(n * m² * target)。
• 可优化：在转移时，枚举上一个颜色 p 时可以分两种情况（颜色相同、颜色不同），用两个数组记录上一个房子的最小成本，可降至 O(n * m * target)。但为清晰，先按朴素方法理解。

举例演算

输入例子：

houses = [0,0,0,0,0]
cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
m = 2, target = 3

初始化 i=0：
dp[0][0][1] = 1（颜色1成本）
dp[0][1][1] = 10（颜色2成本）

i=1, 颜色 j=0：

• 上一个颜色 p=0，街区数 t=1，new_k=1，成本=1+10=11
• 上一个颜色 p=1，街区数 t=1，new_k=2，成本=10+10=20
  记录 dp[1][0][1]=11, dp[1][0][2]=20

i=1, 颜色 j=1：

• 上一个颜色 p=0，t=1，new_k=2，成本=1+1=2
• 上一个颜色 p=1，t=1，new_k=1，成本=10+1=11
  记录 dp[1][1][1]=11, dp[1][1][2]=2

……逐步计算到 i=4（最后一个房子），最后在 target=3 时取最小值 9。

核心要点

1. 状态表示要包含“最后一个房子颜色”和“已形成的街区数”，这样才能在转移时判断街区数是否增加。
2. 已涂色的房子成本固定为 0，但颜色必须匹配。
3. 最终结果必须恰好 target 个街区，不是最多也不是最少。

如果你理解了上述思路，可以尝试用代码实现，并进一步思考如何优化空间复杂度至 O(m * target)。