5431. 給房子涂色 III
在一個(gè)小城市里，有 m 個(gè)房子排成一排，你需要給每個(gè)房子涂上 n 種顏色之一（顏色編號(hào)為 1 到 n ）。有的房子去年夏天已經(jīng)涂過(guò)顏色了，所以這些房子不需要被重新涂色。
我們將連續(xù)相同顏色盡可能多的房子稱(chēng)為一個(gè)街區(qū)。（比方說(shuō) houses = [1,2,2,3,3,2,1,1] ，它包含 5 個(gè)街區(qū) [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）
給你一個(gè)數(shù)組 houses ，一個(gè) m * n 的矩陣 cost 和一個(gè)整數(shù) target ，其中：
houses[i]：是第 i 個(gè)房子的顏色，0 表示這個(gè)房子還沒(méi)有被涂色。
cost[i][j]：是將第 i 個(gè)房子涂成顏色 j+1 的花費(fèi)。
請(qǐng)你返回房子涂色方案的最小總花費(fèi)，使得每個(gè)房子都被涂色后，恰好組成 target 個(gè)街區(qū)。如果沒(méi)有可用的涂色方案，請(qǐng)返回 -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
解釋?zhuān)悍孔油可桨笧?[1,2,2,1,1]
此方案包含 target = 3 個(gè)街區(qū)，分別是 [{1}, {2,2}, {1,1}]。
涂色的總花費(fèi)為 (1 + 1 + 1 + 1 + 5) = 9。
解題思路：
- 簡(jiǎn)單的動(dòng)態(tài)規(guī)劃，我們可以從左向右依次涂色，動(dòng)歸方程為：
dp[i][j][k] = {cost}
第i個(gè)房子，使用第j種顏色，形成第k個(gè)街區(qū)的最小花費(fèi)cost
= min(第i-1個(gè)房子也使用顏色j + 街區(qū)數(shù)不變，)
dp[i][j][k] = min(dp[i-1][顏色 == j][k], min{ dp[i-1][枚舉所有顏色!=j][k-1], ...}) + cost[i][j];
- 當(dāng)然還有一種特殊場(chǎng)景，房子數(shù)量只有1個(gè)，顏色數(shù)也只有n種，此時(shí)的動(dòng)歸方程為：
dp[1][ j ][1] = min{dp[0][1][0], dp[0][2][0], ... , dp[0][n][0]} + cost[0][ j-1]
- 最后 遍歷所有 n 種涂色方案中，m個(gè)房子，target個(gè)街區(qū)的最小花費(fèi)。
class Solution {
public:
/**
dp[i][j][k] = {cost}
第i個(gè)房子，使用第j種顏色，形成第k個(gè)街區(qū)的最小花費(fèi)cost
= min(第i-1個(gè)房子也使用顏色j + 街區(qū)數(shù)不變，)
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 房子個(gè)數(shù)
// n <= 20 顏色種數(shù)
// target <= 100 形成的街區(qū)數(shù)
int dp[105][25][105];
memset(dp, 0x7f, sizeof(dp));
// real_max = 100*10^4
const int MAX_INF = 0x7f7f7f7f;
/** 因?yàn)榍『眯纬蓆arget個(gè)街區(qū)，這里需要設(shè)置初始有效狀態(tài)：
* 1 初始有效狀態(tài): 0個(gè)房子,形成0個(gè)街區(qū)是合法狀態(tài) (此時(shí)顏色有多少都不產(chǎn)生影響)
*
* Q: 為啥要把init所有的顏色的初始狀態(tài)？
* A: 因?yàn)橐粋€(gè)房子對(duì)應(yīng)不同顏色z有不通的cost,比如1個(gè)房子(即只能形成1個(gè)街區(qū))的最小花費(fèi)：
* d[1][j][1] = min(dp[0][前一個(gè)房子顏色 == j][1], min{ dp[0][前一個(gè)房子顏色!=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 房子總數(shù)
for(int j = 1; j<= n; ++j){//顏色總數(shù)
for(int k=1; k<= target; ++k){ //形成的街區(qū)數(shù)
int cur_house_color = j;
int cur_house_cost = cost[i-1][j-1];
//如果當(dāng)前房子不用上色
if(houses[i-1] != 0) {
cur_house_color = houses[i-1];
cur_house_cost = 0;
}
int min_cost = MAX_INF;
//第i個(gè)房子使用第j種顏色，形成k個(gè)街區(qū) dp[i-1][z][k]
// 檢查上一個(gè)房子的各種涂色方案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個(gè)房子，target個(gè)街區(qū)的最小花費(fèi)
for(int z = 1; z<=n ; z++){
ans = std::min(ans, dp[m][z][target]);
}
return (ans < MAX_INF?ans:-1);
}
};
