题目描述

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

Given an array houses, an m * n matrix cost and an integer target where:

• houses[i]: is the color of the house i, 0 if the house is not painted yet.
• cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.

样例

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Constraints:

• 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

算法

(动态规划)

用d[i][j][k]表示将第i个房子涂成颜色j组成k个街区的最小花费。

首先需要区分第i个房子有没有被涂色：

• 第i个房子已经被涂色：那么它的最小花费和前一个房子的涂色有关
  前一个房子的涂色和当前涂色一样：那么从d[i-1][j][k]转移过来，无花费
  前一个房子的涂色和当前涂色不一样：那么从d[i-1][j][k-1]转移过来，无花费
• 第i个房子没有涂色：最小花费仍然和前一个房子的涂色有关
  前一个房子的涂色和当前涂色一样：那么从d[i-1][j][k]转移过来，花费是cost[i-1][j]
  前一个房子的涂色和当前涂色不一样：那么从d[i-1][j][k-1]转移过来，花费是cost[i-1][j]

最终结果是min(d[m][color][target])，其中0 <= color < n，因为并不清楚究竟涂了哪种颜色花费最小，需要对各种颜色遍历一遍取最小值。

无法完成涂色的情况，数组d的所有值初始化为INF，代表初始状态都无最优值，但是d[0][j][0]表示初始没有房子涂了颜色，组成0个街区，应该初始化为0。取最优值的时候，如果遍历完所有颜色还是INF，那么说明无法完成涂，返回-1即可。

时间复杂度$O(m \times n^2 \times \text{target})$。

C++ 代码

class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        const int INF = 0x0ffffff;
        vector<vector<vector<int>>> d(105, vector<vector<int>>(25, vector<int>(target + 5, INF)));

        for (int i = 0; i < n; ++i) d[0][i][0] = 0;

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

        int res = INF;
        for (int i = 0; i < n; ++i) res = min(res, d[m][i][target]);

        return res == INF ? -1 : res;
    }
};