文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

假如有一排房子，共 n 個(gè)，每個(gè)房子可以被粉刷成紅色、藍(lán)色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其與相鄰的兩個(gè)房子顏色不能相同。

當(dāng)然，因?yàn)槭袌?chǎng)上不同顏色油漆的價(jià)格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個(gè)房子粉刷成不同顏色的花費(fèi)是以一個(gè) n x 3 的矩陣來(lái)表示的。

例如，costs[0][0] 表示第 0 號(hào)房子粉刷成紅色的成本花費(fèi)；costs[1][2] 表示第 1 號(hào)房子粉刷成綠色的花費(fèi)，以此類(lèi)推。請(qǐng)你計(jì)算出粉刷完所有房子最少的花費(fèi)成本。

注意： 所有花費(fèi)均為正整數(shù)。示例： 輸入: [[17,2,17],[16,16,5],[14,3,19]] 輸出: 10 解釋: 將 0 號(hào)房子粉刷成藍(lán)色，1 號(hào)房子粉刷成綠色，2 號(hào)房子粉刷成藍(lán)色。最少花費(fèi): 2 + 5 + 3 = 10。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/paint-house
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類(lèi)似題目：LeetCode 265. 粉刷房子 II（DP）

• dp[i][c] 表示刷完 i 房子后，i 房子是 c 顏色時(shí)，花費(fèi)最小多少

class Solution { public:int minCost(vector<vector<int>>& costs) {int n = costs.size(), house, color;if(n==0) return 0;vector<vector<int>> dp(n,vector<int>(3,INT_MAX));dp[0] = costs[0];for(house = 1; house < n; house++){for(color = 0; color < 3; ++color){dp[house][color] = min(dp[house][color], costs[house][color]+min(dp[house-1][(color+1)%3], dp[house-1][(color+2)%3]));}}return min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]));} };

12 ms 9.5 MB

---

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)，一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 256. 粉刷房子（DP）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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