题目描述

在一个小城市里，有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 。

样例

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

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

输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5

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

算法分析

状态表示:

• f[i,j,k]表示从前i个房子中涂，且当前有j个街区，且第i个房子涂的颜色是k的最小值（房子从0开始）

状态计算：

根据最后一个房子涂什么颜色进行划分

• 1、若第i个房子已经确定了涂第k的颜色（不需要花费钱），从1到n中枚举第i - 1个房子涂的颜色u

  • 若u == k，则f[i,j,k] = min(f[i,j,k] , f[i - 1,j,u])
  • 若u != k，则f[i,j,k] = min(f[i,j,k],f[i - 1,j - 1,u])

• 2、若第i个房子没有确定涂的颜色，需要对第i个房子进行涂色（需要花费钱涂色），从1到n中枚举第i个房子涂的颜色k，再从1到n中枚举第i - 1个房子涂的颜色u

  • 若u == k，则f[i,j,k] = min(f[i,j,k] , f[i - 1,j,u] + cost[i][k - 1])
  • 若u != k，则f[i,j,k] = min(f[i,j,k],f[i - 1,j - 1,u] + cost[i][k - 1])

初始化：

• 1、先将f[i,j,k]初始化为无穷大，避免无效数据转移影响结果
• 2、初始化第0个房子的状态值
  • 若第0个房子已经涂色，则初始化f[0,1,houses[0]] = 0
  • 若第0个房子没有涂色，则枚举第0个房子涂1到n的颜色，f[0,1,i] = cost[0][i - 1]，i属于[1,n]

结果:

• f[m - 1,target,k]的最小值，k属于[1,n]

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

Java 代码

class Solution {

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        int[][][] f = new int[105][105][25];
        for(int i = 0;i < m;i ++)
            for(int j = 0;j <= m;j ++) //街区用到0到m
                Arrays.fill(f[i][j],0x3f3f3f3f);

        //初始化
        if(houses[0] != 0) f[0][1][houses[0]] = 0;
        else
        {
            for(int i = 1;i <= n;i ++)
            {
                f[0][1][i] = cost[0][i - 1];
            }

        }

        for(int i = 1;i < m;i ++)
            for(int j = 1;j <= target;j ++)
            {
                //第i个房子已经有颜色
                if(houses[i] != 0)
                {
                    int k = houses[i];
                    for(int u = 1;u <= n;u ++)
                    {
                        if(u == k) f[i][j][k] = Math.min(f[i][j][k],f[i - 1][j][u]);
                        else f[i][j][k] = Math.min(f[i][j][k],f[i - 1][j - 1][u]);
                    }
                }
                //第i个房子没有颜色
                else
                {
                    //枚举第i个房子涂什么颜色
                    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][u] + cost[i][k - 1]);
                            else f[i][j][k] = Math.min(f[i][j][k],f[i - 1][j - 1][u] + cost[i][k - 1]);
                        }
                }
            }
        int res = 0x3f3f3f3f;
        for(int i = 1;i <= n;i ++) res = Math.min(res,f[m - 1][target][i]);
        if(res == 0x3f3f3f3f) return -1;
        return res;
    }
}