闫氏DP分析大法好

C ++代码

class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int INF = 1e8;
        vector<vector<vector<int>>> f(m, vector<vector<int>>(m + 1, vector<int>(n + 1, INF)));

        if (houses[0]) f[0][1][houses[0]] = 0; //第一个房子有颜色
        else
        {
            for (int i = 1; i <= n; i ++) //枚举当前房子上的颜色
                f[0][1][i] = cost[0][i - 1];
        }

        for (int i = 1; i < m; i ++) //枚举房子
            for (int j = 1; j <= target; j ++) //枚举街区数
            {
                if (houses[i]) //已经有颜色
                {
                    int k = houses[i]; //当前颜色
                    for (int u = 1; u <= n; u ++) //枚举上一个颜色
                    {
                        if (u == k) f[i][j][k] = min(f[i][j][k], f[i - 1][j][u]); //街区数相同
                        else f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u]); //街区数加一
                    }
                }
                else
                {
                    for (int k = 1; k <= n; k ++) //枚举当前颜色
                        for (int u = 1; u <= n; u ++) //枚举上一个颜色
                        {
                            if (k == u) f[i][j][k] = min(f[i][j][k], f[i - 1][j][u] + cost[i][k - 1]); //街区不变
                            else f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][u] + cost[i][k - 1]); //街区加一
                        }
                }
            }

        int res = INF;
        for (int i = 1; i <= n; i ++) res = min(res, f[m - 1][target][i]);
        if (res == INF) res = -1;

        return res;
    }
};