【5.4】LeetCode每日一题· 粉刷房子 III

2021年05月04日 16时24分

标签： LeetCode 动态规划

## 题目描述

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

#### 来源

> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/paint-house-iii%0A)

## 解题思路
动态规划，详细思路请见代码。

## 代码
```cpp
class Solution {
public:
    /**
    
    dp[i][j][k] := [0, i]个房子中，第i间房子涂成第j种颜色，且组成编号为[0..k]个街区的最小花费
    讨论第i+1间房子是否已被涂色：
    1. 第i+1间房子已被涂色，即houses[i] != 0。设j = houses[i]
        此时，由于房子不能重复涂色，因此当第i间房子的颜色为j时，不会新增加街区的数目，有状态转移方程：
        dp[i+1][j][k] = dp[i][j][k];
        当第i间房子的颜色不为j时，会将街区的数目增加1，即
        dp[i+1][j][k] = min{dp[i][j0][k-1]} forall j0 != j;
    2. 第i+1间房子未被涂色，即houses[i] = 0
        此时，可以对房子进行任意涂色，如果将第i+1间房子涂成和第i间房子一样的颜色，则有
        dp[i+1][j][k] = dp[i][j][k] + cost[i+1][j];
        如果将第i+1间房子涂成和第i间房子不一样的颜色，则会新增1的街区数目，因此有
        dp[i+1][j][k] = min{dp[i][j0][k-1]} + cost[i+1][j] for j0 != j
    初始条件分析：
    1. 将dp数组初始化为INF
    2. 当i = 0时，k的取值只能是0，如果第i间房子已被涂色，即houses[0] != 0, 设j = houses[i], 那么有
        dp[0][j][0] = 0;
        dp[0][j0][0] = INF for j0 != j
        如果第i间房子没有被涂色，则有
        dp[0][j][0] = cost[0][j] forall j
    最后答案即为min{dp[m-1][j][target-1]} forall j, 如果答案为INF则返回-1
    **/

int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int dp[m][n][target];
        memset(dp, 0x3f, sizeof(dp));

for(int& color: houses){
            color--;
        }
        // 第一个房子已经涂上了颜色，则不用花费
        if(houses[0] != -1){
            dp[0][houses[0]][0] = 0;
        }else{
            for(int j = 0; j < n; j++){
                dp[0][j][0] = cost[0][j];
            }
        }

for(int i = 0; i < m-1; i++){
            for(int j = 0; j < n; j++){
                // 当前房子已涂上颜色，但遍历到的颜色不是已涂上的那一种颜色
                if(houses[i+1] != -1 && houses[i+1] != j){
                    continue;
                }
                for(int k = 0; k < target; k++){
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);            
                    if(k > 0){
                        for(int j0 = 0; j0 < n; j0++){
                            if(j0 != j){
                                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j0][k-1]);
                            }
                        }

}
                    
                    if(dp[i+1][j][k] != 0x3f3f3f3f && houses[i+1] == -1){
                        dp[i+1][j][k] += cost[i+1][j];
                    }
                }
            }
        }
        int res = 0x3f3f3f3f;
        for(int j = 0; j < n; j++){
            res = min(res, dp[m-1][j][target-1]);
        }
        if(res == 0x3f3f3f3f) return -1;
        return res;
    }
};
```

## 用时和内存
> 执行用时：56 ms，在所有 C++提交中击败了81.33%的用户
> 内存消耗：10.3 MB，在所有 C++提交中击败了95.33%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.4】LeetCode每日一题· 粉刷房子 III

所有评论

暂无评论

新增评论