线性动态规划：粉刷房子 III

题目描述

假设你有一个共 n 个房子的街道，每个房子可以涂成 m 种颜色之一（颜色编号从 1 到 m）。部分房子已经涂过颜色（用 houses[i] 表示，若为 0 表示未涂色），其余未涂色的房子需要你选择颜色。涂色成本用一个 n x m 的矩阵 cost 表示，其中 cost[i][j] 表示将房子 i 涂成颜色 j+1 的代价。

此外，街道被划分为若干街区（neighborhood），定义如下：若连续若干房子颜色相同，则它们属于同一个街区。最终要求涂色完成后恰好形成 target 个街区。

请计算满足恰好 target 个街区的最小涂色成本。如果无法做到，返回 -1。

示例

n = 4, m = 3, target = 3
houses = [0,0,0,0]  # 全部未涂色
cost = [[1,10,20],[5,2,3],[7,1,6],[4,3,1]]
输出：最小成本为 6（方案：颜色 [1,2,1,3]，街区数 = 3，成本=1+2+1+1=6）

解题思路

这是一个三维动态规划问题，需要同时记录：

1. 当前处理到的房子索引 i（0 ≤ i < n）
2. 当前已形成的街区数 k（1 ≤ k ≤ target）
3. 当前房子的颜色 c（1 ≤ c ≤ m）

状态定义
设 dp[i][k][c] 表示涂完前 i+1 个房子（0~i），且第 i 个房子颜色为 c，此时共有 k 个街区的最小成本。

状态转移
考虑从房子 i-1 到房子 i 的涂色情况：

• 若 houses[i] != 0（已涂色），则当前房子颜色固定为 houses[i]，不能选择其他颜色。
• 若 houses[i] == 0（未涂色），则可选择任意颜色 c（1 ≤ c ≤ m），成本增加 cost[i][c-1]。

对于第 i 个房子的颜色 c 与第 i-1 个房子的颜色 prevC：

• 如果 c == prevC，则房子 i 与 i-1 属于同一街区，街区数不变：
  dp[i][k][c] = min(dp[i][k][c], dp[i-1][k][prevC] + cost[i][c-1])
• 如果 c != prevC，则房子 i 新开一个街区，街区数增加 1：
  dp[i][k][c] = min(dp[i][k][c], dp[i-1][k-1][prevC] + cost[i][c-1])

初始化

• 对于第一个房子（i=0）：
  • 如果已涂色（houses[0] != 0），则颜色固定为 c0 = houses[0]，街区数 k=1，成本为 0（因为颜色已定，无需额外成本？注意：已涂色房子成本为0，但题目中已涂色房子不能更改，所以成本不计入，但未涂色才加 cost）。实际上，已涂色房子对应的 dp[0][1][c0] = 0，其他颜色不可达（设为无穷大）。
  • 如果未涂色，则可涂任意颜色 c，成本为 cost[0][c-1]，街区数 k=1。

最终答案
遍历最后一个房子（i=n-1）的所有颜色 c，取 dp[n-1][target][c] 的最小值。如果全部为无穷大，则返回 -1。

详细步骤与例子

以示例数据逐步计算：

n=4, m=3, target=3
houses = [0,0,0,0]
cost = [[1,10,20], [5,2,3], [7,1,6], [4,3,1]]

1. 初始化（i=0）：

   • 房子0未涂色，可涂颜色1,2,3，街区数k=1。
   • dp[0][1][1] = cost[0][0] = 1
   • dp[0][1][2] = 10
   • dp[0][1][3] = 20

2. 处理房子1（i=1）：

   • 对每个可能的颜色 c（1..3），对每个可能的 prevC（1..3），更新 k=1,2。
   • 例：c=1, prevC=1 → k 不变：dp[1][1][1] = min(..., dp[0][1][1] + cost[1][0]=1+5=6)
   • c=1, prevC=2 → k 增加：dp[1][2][1] = min(..., dp[0][1][2] + cost[1][0]=10+5=15)
   • 类似计算所有组合，更新 dp[1][k][c]。

3. 处理房子2（i=2）：

   • 同样枚举 c 和 prevC，更新 k=1..3。
   • 注意 k 不能超过 i+1（因为最多 i+1 个街区）。

4. 处理房子3（i=3）：

   • 当 k=3 时，只有 c ≠ prevC 才可能从 k=2 转移来。
   • 最终找到 dp[3][3][1] = 1+2+1+? 等组合，最小为 6（颜色方案 [1,2,1,3] 成本 1+2+1+1=6）。

优化与实现细节

• 初始状态：dp 设为一个大数（如 float('inf')），表示不可达。
• 已涂色房子：若尝试的颜色 c ≠ houses[i]，则跳过。
• 时间复杂度：O(n × target × m²)，可通过循环顺序优化（先 i，再 k，然后 c 和 prevC）。
• 空间优化：由于 dp[i] 只依赖 dp[i-1]，可滚动数组压缩为二维（O(target × m)）。

核心代码框架（Python）

def minCost(houses, cost, n, m, target):
    dp = [[[float('inf')] * (m+1) for _ in range(target+1)] for _ in range(n)]
    # 初始化 i=0
    if houses[0] != 0:
        dp[0][1][houses[0]] = 0
    else:
        for c in range(1, m+1):
            dp[0][1][c] = cost[0][c-1]
    
    for i in range(1, n):
        for k in range(1, target+1):
            for c in range(1, m+1):
                if houses[i] != 0 and houses[i] != c:
                    continue  # 颜色固定，不匹配则跳过
                add_cost = 0 if houses[i] != 0 else cost[i][c-1]
                for prevC in range(1, m+1):
                    if prevC == c:
                        dp[i][k][c] = min(dp[i][k][c], dp[i-1][k][prevC] + add_cost)
                    else:
                        if k > 1:
                            dp[i][k][c] = min(dp[i][k][c], dp[i-1][k-1][prevC] + add_cost)
    
    ans = min(dp[n-1][target][c] for c in range(1, m+1))
    return ans if ans != float('inf') else -1