LeetCode 1473. 粉刷房子 III
原题链接
困难
作者:
飞呀
,
2021-05-17 18:54:48
,
所有人可见
,
阅读 201
const int INF = 1e8; //定义无穷大
class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
vector<vector<vector<int>>> f(m, vector<vector<int>>(target+1, vector<int>(n+1, INF)));
//f[i][j][k]表示将1-i染色,构成了j组,最后一个房子的颜色是k。
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(u == k){
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;
}
};