【Day08】1473.粉刷房子III

1473. 粉刷房子 III

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

题解·:

很明显的DP

  1. 设状态 f(i,j,k) 表示处理了前 i 个房屋,有 j 个社区,最后一个房屋的颜色为 k 的最小花费,其中房屋的有效下标从 1 开始。建立辅助数组 g(i,j,k) 表示同样含义下,最后一个房屋颜色 不是 k 的最小花费。

  2. 初始时,f(0,0,k)=g(0,0,k)=0,其余为正无穷或者待定。
    转移时,分两种情况

  3. 如果第 i 个房屋已经有了颜色 c,则有两种选择,上一个房屋颜色为 c 或者不为 c,转移
    $$
    f(i, j, c)=\min (f(i-1, j, c), g(i-1, j-1, c))
    $$

  4. 如果第 i 个房屋没有颜色,则枚举一个颜色 k,然后同样根据上一个房屋的颜色,转移
    $$
    f(i, j, k)=\min (f(i-1, j, k), g(i-1, j-1, k))+\operatorname{cost}(i, k-1)_{\text {。 }}
    $$

  5. 对于 g 数组的维护如下,假设当前需要维护前 i 个房屋且有 j 个社区下的 g 数组,则我们找 f(i,j,k) 中的最小值 m1 和次小值 m2。如果 m1=m2,则说明对于所有 k, g(i,j,k)=m1;否则,对于 f(i,j,k0)=m1 的那个 k0,其 g(i,j,k0)=m2g,其余 k≠k0都有 g(i,j,k)=m1。

  6. 最终答案为
    $$
    \min (f(m, \text { target }, k)
    $$

class Solution {
public:
    int minCost(vector& houses, vector>& cost, int m, int n, int target) {
        const int MAX = 0x3f3f3f3f;
        const int M = 110;
        const int N = 30;

        int f[M][M][N], g[M][M][N];
        memset(f, 0x3f, sizeof(f));
        memset(g, 0x3f, sizeof(g));

        for (int k = 1; k <= n; k++)
            f[0][0][k] = g[0][0][k] = 0;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= min(i, target); j++) {
                if (houses[i - 1] > 0) {
                    int c = houses[i - 1];
                    f[i][j][c] = min(f[i - 1][j][c], g[i - 1][j - 1][c]);
                } else {
                    for (int k = 1; k <= n; k++)
                        f[i][j][k] = min(f[i - 1][j][k], g[i - 1][j - 1][k])
                                        + cost[i - 1][k - 1];
                }

                int m1 = MAX, m2 = MAX;
                for (int k = 1; k <= n; k++)
                    if (m1 > f[i][j][k]) {
                        m2 = m1;
                        m1 = f[i][j][k];
                    } else if (m2 > f[i][j][k])
                        m2 = f[i][j][k];

                if (m1 == m2) {
                    for (int k = 1; k <= n; k++)
                        g[i][j][k] = m1;
                } else {
                    for (int k = 1; k <= n; k++)
                        if (f[i][j][k] == m1) g[i][j][k] = m2;
                        else g[i][j][k] = m1;
                }
            }

        int ans = MAX;
        for (int k = 1; k <= n; k++)
            ans = min(ans, f[m][target][k]);

        if (ans == MAX)
            ans = -1;

        return ans;
    }
};

   转载规则


《【Day08】1473.粉刷房子III》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day09】740.删除并获得点数 【Day09】740.删除并获得点数
740. 删除并获得点数给你一个整数数组 nums ,你可以对它进行一些操作。 每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除每个等于 nums[i] - 1 或 nums[i] + 1
2021-05-05
下一篇 
【Day07】7.整数反转 【Day07】7.整数反转
7. 整数反转给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。 假设环境不允许存储 64 位整数(有符号或无符号)
2021-05-03
  目录