LeetCode 1473. 粉刷房子 III
原题链接
困难
作者:
ITNXD
,
2021-05-06 23:37:34
,
所有人可见
,
阅读 222
详细请查看注释
参考代码:
class Solution {
public:
/*
cost数组:下标为i房子染成第j种颜色的花费!第j种颜色的下标为j - 1
状态表示:f[i][j][k]表示前i个房子(下标从0开始)分为j组(下标从1开始)且下标为i房子被染为第k种颜色(下标从1开始)。属性为最小花费!
状态计算:考虑下标为i - 1个房子可以染的颜色u!(u可取1,2,3...n)
1. 若下标为i的房子已经染色(k = house[i])
1. 若u == k:f[i][j][k] = f[i - 1][j][u]
2. 若u != k:f[i][j][k] = f[i - 1][j - 1][u]
2. 若下标为i的房子未染色 (k = 1,2,3...n)
1. 若u == k:f[i][j][k] = f[i - 1][j][u] + cost[i][k - 1]
2. 若u != k:f[i][j][k] = f[i - 1][j - 1][u] + cost[i][k - 1]
最终答案:f[m - 1][target][k] (k取值为1,2,3...n)的最小值!
*/
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
int INF = 1e9;
vector<vector<vector<int>>> f(m, vector<vector<int>>(target + 1, vector<int>(n + 1, INF)));
// 初始化0号房子染色情况
if(houses[0]) f[0][1][houses[0]] = 0; // 0号房子分为1组染色为house[0]的代价为0
else {
for(int k = 1; k <= n; k ++) // 枚举0号房子染色情况
f[0][1][k] = cost[0][k - 1];
}
for(int i = 1; i < m; i ++)
for(int j = 1; j <= target; j ++)
if(houses[i]){ // 该房子已染色
int k = houses[i]; // 下标为i房子染色情况已经确定为house[i]!
for(int u = 1; u <= n; u ++) // 枚举下标为i - 1房子染色情况
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 ++) // 枚举下标为i房子染色情况
for(int u = 1; u <= n; u ++) // 枚举下标为i - 1房子染色情况
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 k = 1; k <= n; k ++) res = min(res, f[m - 1][target][k]);
if(res == INF) return -1;
return res;
}
};