算法1

(DP) $O(mn)$

C++ 代码

class Solution {
private:
    int f[101][101][21];
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int MAXC = 0x3f3f3f3f;
        memset(f, 0x3f, sizeof f);
        for(int c = 1; c <= n; c++) f[0][0][c] = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= min(i, target); j++) {
                if(houses[i-1]) {
                    int c = houses[i-1];
                    for(int pc = 1; pc <= n; pc++) {
                        f[i][j][c] = min(f[i][j][c], pc == c ? f[i-1][j][pc] : f[i-1][j-1][pc]);
                    }
                } else {
                    for(int c = 1; c <= n; c++) {
                        for(int pc = 1; pc <= n; pc++) {
                            f[i][j][c] = min(f[i][j][c], pc == c 
                            ? f[i-1][j][pc] + cost[i-1][c-1] 
                            : f[i-1][j-1][pc] + cost[i-1][c-1]);
                        }
                    }
                }
            }
        }
        int ans = MAXC;
        for(int c = 1; c <= n; c++)
            ans = min(ans, f[m][target][c]);
        return ans == MAXC ? -1 : ans;
    }
};


// 正常来说，DFS的做法是这样的：
// 每一步，status = nebcnt, cost, i
// 1.1 对于有颜色的，更新neb
// 1.2 对于无颜色的，选择一个颜色，更新neb和费用
// 2 最后递归下一步

// 递归的终止条件：
// 1. neb超过target
// 2. 遍历完成，更新min cost

// DFS有什么问题呢？时间复杂度 = m ** n = 100e20 = 1e22 超时。。。

// f(i, nebcnt, c): 前i个房子，总共nebcnt个街区，第i个房子是颜色c
// 属性：min_cost : int
// 转换公式
// if houses[i] == 0:
//  f(i,neb,color) = min(f(i-1,neb,color) + houses[i][color]), f(i-1, neb-1, c in colors) + houses[i][c]))
// if houses[i] != 0:
//  f(i, neb,color) = min(f(i-1,neb,color), f(i-1, neb-1, c in colors))