5431. 给房子涂色 III
在一个小城市里,有 m 个房子排成一排,你需要给每个房子涂上 n 种颜色之一(颜色编号为 1 到 n )。有的房子去年夏天已经涂过颜色了,所以这些房子不需要被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。(比方说 houses = [1,2,2,3,3,2,1,1] ,它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。)
给你一个数组 houses ,一个 m * n 的矩阵 cost 和一个整数 target ,其中:
houses[i]:是第 i 个房子的颜色,0 表示这个房子还没有被涂色。
cost[i][j]:是将第 i 个房子涂成颜色 j+1 的花费。
请你返回房子涂色方案的最小总花费,使得每个房子都被涂色后,恰好组成 target 个街区。如果没有可用的涂色方案,请返回 -1 。
示例 1:
输入:houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出:9
解释:房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区,分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。
解题思路:
- 简单的动态规划,我们可以从左向右依次涂色,动归方程为:
dp[i][j][k] = {cost}
第i个房子,使用第j种颜色,形成第k个街区的最小花费cost
= min(第i-1个房子也使用颜色j + 街区数不变,)
dp[i][j][k] = min(dp[i-1][颜色 == j][k], min{ dp[i-1][枚举所有颜色!=j][k-1], ...}) + cost[i][j];
- 当然还有一种特殊场景,房子数量只有1个,颜色数也只有n种,此时的动归方程为:
dp[1][ j ][1] = min{dp[0][1][0], dp[0][2][0], ... , dp[0][n][0]} + cost[0][ j-1]
- 最后 遍历所有 n 种涂色方案中,m个房子,target个街区的最小花费。
class Solution {
public:
/**
dp[i][j][k] = {cost}
第i个房子,使用第j种颜色,形成第k个街区的最小花费cost
= min(第i-1个房子也使用颜色j + 街区数不变,)
dp[i][j][k] = min(dp[i-1][颜色 == j][k], min{ dp[i-1][枚举所有颜色!=j][k-1], ...}) + cost[i][j];
*/
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
// m <=100 房子个数
// n <= 20 颜色种数
// target <= 100 形成的街区数
int dp[105][25][105];
memset(dp, 0x7f, sizeof(dp));
// real_max = 100*10^4
const int MAX_INF = 0x7f7f7f7f;
/** 因为恰好形成target个街区,这里需要设置初始有效状态:
* 1 初始有效状态: 0个房子,形成0个街区是合法状态 (此时颜色有多少都不产生影响)
*
* Q: 为啥要把init所有的颜色的初始状态?
* A: 因为一个房子对应不同颜色z有不通的cost,比如1个房子(即只能形成1个街区)的最小花费:
* d[1][j][1] = min(dp[0][前一个房子颜色 == j][1], min{ dp[0][前一个房子颜色!=j][0], ...}) + cost[0][j];
*/
for(int j = 0; j<=n; ++j){
dp[0][j][0] = 0;
}
for(int i =1; i<= m; ++i){ //m 房子总数
for(int j = 1; j<= n; ++j){//颜色总数
for(int k=1; k<= target; ++k){ //形成的街区数
int cur_house_color = j;
int cur_house_cost = cost[i-1][j-1];
//如果当前房子不用上色
if(houses[i-1] != 0) {
cur_house_color = houses[i-1];
cur_house_cost = 0;
}
int min_cost = MAX_INF;
//第i个房子使用第j种颜色,形成k个街区 dp[i-1][z][k]
// 检查上一个房子的各种涂色方案z
for(int z = 1; z <= n; ++z){
if(z != cur_house_color || (i==1)){
min_cost = std::min(min_cost, dp[i-1][z][k-1]);
//printf("xx dp[%d][%d][%d]\n", i-1, z, k-1);
} else {
min_cost = std::min(min_cost, dp[i-1][z][k]);
//printf("==> dp[%d][%d][%d]\n", i-1, z,k);
}
}
dp[i][cur_house_color][k] = (min_cost + cur_house_cost);
}
}
}
int ans = MAX_INF;
//3 遍历所有 n 种涂色方案中,m个房子,target个街区的最小花费
for(int z = 1; z<=n ; z++){
ans = std::min(ans, dp[m][z][target]);
}
return (ans < MAX_INF?ans:-1);
}
};
网友评论