解题思路

$DP$

• 用$f[i][j][k]$表示集合：第$i$个房子，使用第$j$种颜色，能够形成$k$个区域的花费，属性为最小
• 若$houses[i] \neq 0$说明本身有颜色，根据$i$和$i-1$的颜色是否相同进行状态转移：相同，直接转移；不同则枚举$i-1$房子的颜色转移
• 若$houses[i] = 0$说明无颜色，则枚举颜色。在枚举颜色内部则就转移到了上面的状态。
• 根据定义出发从$f[m][1\sim n][target]$中选择最小值即可，找不到则返回$-1$。

代码

class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int INF = 0x3f3f3f3f;
        vector<vector<vector<int>>> f(m , vector<vector<int>> (n + 1, vector<int> (target + 1, INF)));
        if(houses[0] != 0) f[0][houses[0]][1] = 0;
        else {
            for(int i = 0; i < n; ++i) f[0][i + 1][1] = cost[0][i];
        }
        for(int i = 1; i < m; ++i) {
            if(houses[i] != 0) {
                int j = houses[i];
                for(int k = 1; k <= target; ++k) {
                    for(int p = 1; p <= n; ++p) {
                        if(j == p) f[i][j][k] = min(f[i][j][k], f[i - 1][p][k]);
                        else f[i][j][k] = min(f[i][j][k], f[i - 1][p][k - 1]);
                    }
                }
            } else {
                for(int j = 1; j <= n; ++j) {
                    for(int k = 1; k <= target; ++k) {
                        for(int p = 1; p <= n; ++p) {
                            if(j == p) f[i][j][k] = min(f[i][j][k], f[i - 1][p][k] + cost[i][j - 1]);
                            else f[i][j][k] = min(f[i][j][k], f[i - 1][p][k - 1] + cost[i][j - 1]);
                        }
                    }
                }
            }
        }
        int res = INF;
        for(int i = 1; i <= n; ++i) res = min(res, f[m - 1][i][target]);
        if(res == INF) res = -1;
        return res;
    }
};

参考

闫式$DP$分析法