题目描述

在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区  [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * 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 = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

样例4

输入：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

算法1

(DFS) TLE

• 从左到右考虑每个位置，如果能涂颜色，就考虑把每种颜色都涂一遍；如果不能涂颜色，则涂下一个位置

• DFS函数的参数：

  1. 当前涂到第u个房子
  2. 当前已经构成了cnt个街区
  3. 上一个房子涂成last颜色
  4. 涂完当前这个房子已经花费了sum

• 时间复杂度：$O(n^m)$，n为颜色数量，m为房子数量

Java 代码

class Solution {
    final int INF = 0x3f3f3f3f;
    int[] hs;
    int[][] cost;
    int m, n, target, res = INF;
    public int minCost(int[] hs, int[][] cost, int m, int n, int target) {
        this.hs = hs; this.cost = cost; this.m = m; this.n = n; this.target = target;
        dfs(0, 0, 0, 0);
        return res == INF ? -1 : res;
    }

    void dfs(int u, int cnt, int last, int sum){
        if(u == m){
            if(cnt == target){
                res = Math.min(res, sum);
            }
            return;
        }

        if(hs[u] == 0){
            // 可以涂
            // 涂第一间房子
            if(last == 0) {
                // 枚举涂的颜色
                for(int i = 1; i <= n; i++){
                    dfs(u + 1, cnt + 1, i, sum + cost[u][i-1]);
                }
            }else{
                for(int i = 1; i <= n; i++){
                    // 如果涂的颜色和上一次相同，街区数不变
                    if(i == last) dfs(u + 1, cnt, i, sum + cost[u][i-1]);
                    // 如果涂的颜色和上一次不同，街区数+1
                    else dfs(u + 1, cnt + 1, i, sum + cost[u][i-1]);
                }
            }
        }else{
            // 不能涂色
            int k = hs[u];
            // 如果当前颜色与上一次相同，街区数不变
            if(k == last) dfs(u + 1, cnt, k, sum);
            // 如果当前颜色与上一次不同，街区数+1
            else dfs(u + 1, cnt + 1, k, sum);
        }
    }
}

算法2

(记忆化搜索)

• 记忆化搜索的memo数组需要和dp的数组定义一致，dp数组为int类型，所以记忆化搜索的返回值需要返回搜索的花费值

• int dfs(int u, int cnt, int last, int sum)表示从第u个位置往后一直搜到结尾所用到的最小花费，答案记为dfs(0, 0, 0, 0)

• 时间复杂度：$O(m * n^2 * target)$

Java代码

class Solution {
    final int INF = 0x3f3f3f3f;
    int[] hs;
    int[][] cost;
    int m, n, target;
    // -1表示没搜索过
    int[][][] memo = new int[110][110][30];
    public int minCost(int[] hs, int[][] cost, int m, int n, int target) {
        this.hs = hs; this.cost = cost; this.m = m; this.n = n; this.target = target;
        for(int[][] ff: memo){
            for(int[] f: ff){
                Arrays.fill(f, -1);
            }
        }
        int ans = dfs(0, 0, 0, 0);
        return ans == INF ? -1 : ans;
    }

    int dfs(int u, int cnt, int last, int sum){
        if(memo[u][cnt][last] != -1) return memo[u][cnt][last];
        if(u == m){
            if(cnt == target){
                return 0;
            }
            return INF;
        }
        int res = INF;
        if(hs[u] == 0){
            // 可以涂
            if(last == 0) {
                for(int i = 1; i <= n; i++){
                    int cur = dfs(u + 1, cnt + 1, i, sum + cost[u][i-1]);
                    res = Math.min(res, cur + cost[u][i-1]);
                }
            }else{
                for(int i = 1; i <= n; i++){
                    if(i == last){
                        int cur = dfs(u + 1, cnt, i, sum + cost[u][i-1]);
                        res = Math.min(res, cur + cost[u][i-1]);
                    }
                    else {
                        int cur = dfs(u + 1, cnt + 1, i, sum + cost[u][i-1]);
                        res = Math.min(res, cur + cost[u][i-1]);
                    }
                }
            }
        }else{
            // 不能涂色
            int k = hs[u];
            if(k == last) {
                res = Math.min(res, dfs(u + 1, cnt, k, sum));
            }
            else{
                res = Math.min(res, dfs(u + 1, cnt + 1, k, sum));
            } 
        }
        return memo[u][cnt][last] = res;
    }
}

算法3

(动态规划)

• 状态定义：f[i][j][k]表示前i个房子，连成j个街区，第i个房子颜色为k的最小花费

• 状态转移：

  1. hs[i]可以被涂色：f[i][j][k] = min(f[i-1][j-1][u], f[i-1][j][k]), 当u != k
  2. hs[i]不能被涂色：f[i][j][k] = min(f[i-1][j-1][u], f[i-1][j][k]), 当k = hs[i] 且 u != k

• 时间复杂度：$O(m * n^2 * target)$

Java代码

class Solution {
    public int minCost(int[] hs, int[][] cost, int m, int n, int target) {
        // f[i][j][k]: 前i个房子，连成j个街区，第i个房子颜色为k的最小花费
        int INF = 0x3f3f3f3f;
        int[][][] f = new int[m + 1][m + 1][n + 1];
        for(int[][] u: f){
            for(int[] v: u) Arrays.fill(v, INF);
        }
        // 初始化
        for(int i = 1; i <= n; i++){
            f[0][0][i] = 0;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= i; j++){
                if(hs[i-1] == 0){
                    // 可以涂色
                    for(int k = 1; k <= n; k++){
                        for(int u = 1; u <= n; u++){
                            if(k == u){
                                f[i][j][k] = Math.min(f[i][j][k], f[i-1][j][k] + cost[i-1][k-1]);
                            }else{
                                f[i][j][k] = Math.min(f[i][j][k], f[i-1][j-1][u] + cost[i-1][k-1]);
                            }
                        }
                    }
                }else{
                    // 不能涂色
                    int k = hs[i-1];
                    for(int u = 1; u <= n; u++){
                        if(u == k){
                            f[i][j][k] = Math.min(f[i][j][k], f[i-1][j][k]);
                        }else{
                            f[i][j][k] = Math.min(f[i][j][k], f[i-1][j-1][u]);
                        }
                    }
                }
            }
        }
        int res = INF;      
        for(int i = 1; i <= n; i++){
            res = Math.min(res, f[m][target][i]);
        }
        return res == INF ? -1 : res;
    }
}