文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

有n個房子在一列直線上，現(xiàn)在Bob需要給房屋染色，共有k種顏色。
每個房屋染不同的顏色費用也不同，Bob希望有一種染色方案使得相鄰的房屋顏色不同。
但Bob計算了使相鄰房屋顏色不同的最小染色費用，發(fā)現(xiàn)花費非常高。
于是Bob想選擇一個區(qū)間作為主題步行街，在這個區(qū)間中的所有房子必須染成同一個顏色。Bob覺得這樣可能能降低總花費，但是也不想讓這個步行街太長。
Bob認(rèn)為步行街的長度最多為 ‘t’。
但這個花費太難計算，Bob打算交給你來計算。
你能算出將這些房子進行染色的最小花費是多少嗎？

費用通過一個nxk 的矩陣給出，比如costs[0][0]表示房屋0染顏色0的費用，costs[1][2]表示房屋1染顏色2的費用。
t 是一個整數(shù)，表示有最多有多少個房屋顏色相同。

房子總數(shù): 1 <= n <= 100 顏色總數(shù): 1 <= k <= 100 步行街長度上限: 1 <= t <= 10 房屋染色費用: 1 <= cost[i][j] <= 1000示例 樣例1 輸入: costs = [[14,2,11],[11,14,5],[14,3,10]] t = 2 輸出: 10 說明: 三個屋子分別使用第1,2,1種顏色，總花費是10。 在這個樣例中你不需要建造步行街。樣例2 輸入: costs = [[14,2,11],[11,14,5],[14,3,10]] t = 2 輸出: 10 說明： 你可以在[1,2]的區(qū)間中建造一個步行街， 這樣序號為1和2的兩個房子可以染成相同顏色。 因此如果這三個房子的顏色為[2,2,1]，總花費為10. 如果你在[2,3]的區(qū)間中建造一個步行街， 最小的花費是11(1+5+5)，大于10，因此不是最優(yōu)解。 你無法在[1,3]中建造步行街，因為步行街總長度為3，大于t。

來源：https://tianchi.aliyun.com/oj/15179470890799741/85251759933690470

2. 解題

題目意思是最多只能有一個步行街，我理解錯了，以為是不限制

錯誤代碼：

class Solution { public:/*** @param costs: costs of paint ith house into color j* @param t: maximum length of street* @return: minimum costs of painting all houses*/int paintHouseIII(vector<vector<int>> &costs, int t) {// Write your code here.int n = costs.size(), col = costs[0].size(), i, j;vector<vector<vector<int>>> dp(n, vector<vector<int>>(col, vector<int>(t+1, INT_MAX)));// dp[i][c][k] 表示 i房子刷完了，其是 c 顏色，c 顏色連續(xù)了 k 次 的最小花費for(j = 0; j < col; ++j)dp[0][j][1] = costs[0][j];for(i = 1; i < n; ++i){for(int c1 = 0; c1 < col; ++c1){for(int c2 = 0; c2 < col; ++c2){if(c1 != c2){for(int k = 1; k <= t; ++k){if(dp[i-1][c1][k] == INT_MAX)continue;dp[i][c2][1] = min(dp[i][c2][1], costs[i][c2]+dp[i-1][c1][k]);}}else{for(int k = 1; k < t; ++k){if(dp[i-1][c1][k] == INT_MAX)continue;dp[i][c2][k+1] = min(dp[i][c2][k+1], costs[i][c2]+dp[i-1][c1][k]);}}}}}int ans = INT_MAX;for(i = 0; i < col; ++i)for(j = 1; j <= t; ++j)ans = min(ans, dp[n-1][i][j]);return ans;} };

參考大佬的題解：

正確解：

class Solution { public:/*** @param costs: costs of paint ith house into color j* @param t: maximum length of street* @return: minimum costs of painting all houses*/int paintHouseIII(vector<vector<int>> &costs, int t) {// Write your code here.int n = costs.size(), col = costs[0].size(), i, j, k, c1, c2;vector<vector<vector<int>>> dp(n, vector<vector<int>>(col, vector<int>(2, INT_MAX)));// dp[i][c][0 or 1] 表示 i 房子刷完 c 顏色，還沒有步行街0，有步行街1，的最小花費for(j = 0; j < col; ++j)dp[0][j][0] = dp[0][j][1] = costs[0][j];//初始化vector<vector<int>> value(n, vector<int>(n, 0));for(j = 0; j < col; ++j){for(i = 0; i < n; ++i)//房子都刷 j 顏色的花費前綴和{if(i == 0)value[i][j] = costs[i][j];elsevalue[i][j] = value[i-1][j] + costs[i][j];}}for(i = 1; i < n; ++i){for(c1 = 0; c1 < col; ++c1){for(c2 = 0; c2 < col; ++c2){if(c1 != c2)//顏色不一樣{dp[i][c2][0] = min(dp[i][c2][0], dp[i-1][c1][0]+costs[i][c2]);dp[i][c2][1] = min(dp[i][c2][1], dp[i-1][c1][1]+costs[i][c2]);}}//顏色一樣，可以跟前面組成步行街for(j = i-1; j >= 0; --j)//[j, i] 區(qū)間為同一顏色 c1 的步行街{if(i-j+1 > t)break;dp[i][c1][1] = min(dp[i][c1][1], dp[j][c1][0]+value[i][c1]-value[j][c1]);// 前面沒有步行街0， + 加上后面都是 c1 顏色的花費}}}int ans = INT_MAX;for(j = 0; j < col; ++j)ans = min(ans, min(dp[n-1][j][0], dp[n-1][j][1]));return ans;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的阿里云 超级码力在线编程大赛初赛 第3场 题目2. 房屋染色（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。