小旭讲解 LeetCode 1473. Paint House III
小旭讲解 LeetCode 1473. Paint House III

如果大家有兴趣一起侃侃数据结构与算法,那么可以通过下面的微信号或者微信公众号给我留言(要带上自己的微信 ID 哦):
微信公众号(推荐):ihuxublog(胡小旭博客)
微信:genialx
如果你喜欢我的视频,可以到B站或者Youtube关注我~

BiliBili

原题

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

代码

class Solution {
public:
    int minCost(vector<int>& hs, vector<vector<int>>& cost, int m, int n, int target) {
        int f[m + 5][m + 5][n + 5];
        memset(f, 0x3f, sizeof f);
        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) {
                    // 可以涂第i个房子
                    for (int k = 1; k <= n; ++k) {
                        for (int u = 1; u <= n; ++u) {
                            if (u == k) {
                                f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i - 1][u - 1]);
                            } else {
                                f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u] + cost[i - 1][k - 1]);
                            }
                        }
                    }
                } else {
                    // 不可以涂第i个房子
                    int k = hs[i - 1];
                    for (int u = 1; u <= n; ++u) {
                        if (u == k) {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);
                        } else {
                            f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u]);
                        }
                    }
                }
            }
        } 
        int res = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i) res = min(res, f[m][target][i]);
        
        if (res == 0x3f3f3f3f) return -1;
        return res;
    }
};

// f[i][j][k] 前 i 个房子,染成 j 个街区,第 i 个房子的颜色是k的最小花费
// 0 1 ..... i - 1, i
//               u, k
// f[i][j][k] = min{f[i - 1][j][k], f[i - 1][j - 1][u] + cost[i][k]}
// O(m^2 * n^2)

复杂度分析

  • 时间复杂度:O(m^{2} * n^{2})
  • 空间复杂度:O(m^{2} * n)

参考

[1] LeetCode. https://leetcode-cn.com/problems/paint-house-iii/

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-1473-paint-house-iii/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。