Hard

题目描述

在一个小城市里有一排 m 栋房子，每栋房子都必须用 n 种颜色中的一种来粉刷（颜色编号为 1 到 n），其中一些房子去年夏天已经涂过了，不需要重新粉刷。

一个街区是一组连续的、颜色相同的房子组成的最大集合。

例如：houses = [1,2,2,3,3,2,1,1] 包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}]。

给定一个数组 houses，一个 m x n 的矩阵 cost 和一个整数 target，其中：

  • houses[i]：是第 i 栋房子的颜色，如果这栋房子还没有被粉刷则为 0。
  • cost[i][j]：是将第 i 栋房子粉刷成颜色 j+1 的花费。

返回粉刷完所有剩余房子的最少成本，使得恰好有 target 个街区。如果无法实现，返回 -1。

示例 1：

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：将房子粉刷成这样 [1,2,2,1,1]
这个数组包含 target = 3 个街区，[{1}, {2,2}, {1,1}]。
粉刷所有房子的成本为 (1 + 1 + 1 + 1 + 5) = 9。

示例 2：

输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有些房子已经被粉刷了，将房子粉刷成这样 [2,2,1,2,2]
这个数组包含 target = 3 个街区 [{2,2}, {1}, {2,2}]。
粉刷第一栋和最后一栋房子的成本为 (10 + 1) = 11。

示例 3：

输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被粉刷成了 4 个街区 [{3},{1},{2},{3}]，这和 target = 3 不同。

提示：

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

解题思路

这是一个典型的动态规划问题。我们需要考虑三个维度的状态：当前房子的位置、当前房子的颜色、以及到目前为止形成的街区数量。

核心思路：

定义 dp[i][j][k] 表示前 i 栋房子中，第 i 栋房子涂成颜色 j，且形成了 k 个街区的最小成本。

状态转移：

对于第 i 栋房子：

  1. 如果 houses[i-1] != 0（已经涂色），那么颜色已经确定，只需要考虑街区数的变化
  2. 如果 houses[i-1] == 0（未涂色），需要枚举所有可能的颜色

街区数的变化规则：

  • 如果当前房子和前一栋房子颜色相同，街区数不变
  • 如果颜色不同，街区数加1

初始化： 第一栋房子单独处理，根据是否已涂色分别初始化。

优化细节： 使用滚动数组优化空间复杂度，并设置合理的无穷大值来标记不可达状态。

最终答案是所有 dp[m][j][target] 中的最小值。

代码实现

class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int INF = 1e9;
        vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(target + 1, INF)));
        
        // 初始化：第0栋房子，0个街区
        dp[0][0][0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= target; k++) {
                    // 如果房子已经涂色且不是当前颜色j，跳过
                    if (houses[i-1] != 0 && houses[i-1] != j) continue;
                    
                    // 计算涂色成本
                    int paintCost = (houses[i-1] == 0) ? cost[i-1][j-1] : 0;
                    
                    // 从前一个房子转移
                    for (int prev = 0; prev <= n; prev++) {
                        if (dp[i-1][prev][k] == INF && dp[i-1][prev][k-1] == INF) continue;
                        
                        if (prev == j) {
                            // 颜色相同，街区数不变
                            if (dp[i-1][prev][k] != INF) {
                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][prev][k] + paintCost);
                            }
                        } else {
                            // 颜色不同，街区数加1
                            if (k > 0 && dp[i-1][prev][k-1] != INF) {
                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][prev][k-1] + paintCost);
                            }
                        }
                    }
                }
            }
        }
        
        int result = INF;
        for (int j = 1; j <= n; j++) {
            result = min(result, dp[m][j][target]);
        }
        
        return result == INF ? -1 : result;
    }
};

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        INF = float('inf')
        
        # dp[i][j][k] = 前i栋房子，第i栋房子颜色为j，形成k个街区的最小成本
        dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m + 1)]
        
        # 初始化
        dp[0][0][0] = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                for k in range(1, target + 1):
                    # 如果房子已经涂色且不是当前颜色j，跳过
                    if houses[i-1] != 0 and houses[i-1] != j:
                        continue
                    
                    # 计算涂色成本
                    paint_cost = cost[i-1][j-1] if houses[i-1] == 0 else 0
                    
                    # 从前一个房子转移
                    for prev in range(n + 1):
                        if prev == j:
                            # 颜色相同，街区数不变
                            if dp[i-1][prev][k] != INF:
                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][prev][k] + paint_cost)
                        else:
                            # 颜色不同，街区数加1
                            if k > 0 and dp[i-1][prev][k-1] != INF:
                                dp[i][j][k] = min(dp[i][j][k], dp[i-1][prev][k-1] + paint_cost)
        
        result = min(dp[m][j][target] for j in range(1, n + 1))
        return result if result != INF else -1

public class Solution {
    public int MinCost(int[] houses, int[][] cost, int m, int n, int target) {
        const int INF = 1000000000;
        
        int[,,] dp = new int[m + 1, n + 1, target + 1];
        
        // 初始化为INF
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= target; k++) {
                    dp[i, j, k] = INF;
                }
            }
        }
        
        dp[0, 0, 0] = 0;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= target; k++) {
                    // 如果房子已经涂色且不是当前颜色j，跳过
                    if (houses[i-1] != 0 && houses[i-1] != j) continue;
                    
                    // 计算涂色成本
                    int paintCost = (houses[i-1] == 0) ? cost[i-1][j-1] : 0;
                    
                    // 从前一个房子转移
                    for (int prev = 0; prev <= n; prev++) {
                        if (prev == j) {
                            // 颜色相同，街区数不变
                            if (dp[i-1, prev, k] != INF) {
                                dp[i, j, k] = Math.Min(dp[i, j, k], dp[i-1, prev, k] + paintCost);
                            }
                        } else {
                            // 颜色不同，街区数加1
                            if (k > 0 && dp[i-1, prev, k-1] != INF) {
                                dp[i, j, k] = Math.Min(dp[i, j, k], dp[i-1, prev, k-1] + paintCost);
                            }
                        }
                    }
                }
            }
        }
        
        int result = INF;
        for (int j = 1; j <= n; j++) {
            result = Math.Min(result, dp[m, j, target]);
        }
        
        return result == INF ? -1 : result;
    }
}

var minCost = function(houses, cost, m, n, target) {
    const memo = new Map();
    
    function dp(i, neighborhoods, prevColor) {
        if (i === m) {
            return neighborhoods === target ? 0 : Infinity;
        }
        
        if (neighborhoods > target) {
            return Infinity;
        }
        
        const key = `${i},${neighborhoods},${prevColor}`;
        if (memo.has(key)) {
            return memo.get(key);
        }
        
        let result = Infinity;
        
        if (houses[i] !== 0) {
            const color = houses[i];
            const newNeighborhoods = neighborhoods + (color !== prevColor ? 1 : 0);
            result = dp(i + 1, newNeighborhoods, color);
        } else {
            for (let color = 1; color <= n; color++) {
                const newNeighborhoods = neighborhoods + (color !== prevColor ? 1 : 0);
                const paintCost = cost[i][color - 1];
                result = Math.min(result, paintCost + dp(i + 1, newNeighborhoods, color));
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    const answer = dp(0, 0, -1);
    return answer === Infinity ? -1 : answer;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n² × target)
空间复杂度O(m × n × target)

相关题目