LCR 091. 粉刷房子https://leetcode.cn/problems/JEj789/description/

假如有一排房子，共n個(gè)，每個(gè)房子可以被粉刷成紅色、藍(lán)色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個(gè)房子顏色不能相同。當(dāng)然，因?yàn)槭袌?chǎng)上不同顏色油漆的價(jià)格不同，所以房子粉刷成不同顏色的花費(fèi)成本也是不同的。每個(gè)房子粉刷成不同顏色的花費(fèi)是以一個(gè)n x 3的正整數(shù)矩陣costs來表示的。例如，costs[0][0]表示第0號(hào)房子粉刷成紅色的成本花費(fèi)；costs[1][2]表示第1號(hào)房子粉刷成綠色的花費(fèi)，以此類推。請(qǐng)計(jì)算出粉刷完所有房子最少的花費(fèi)成本。

1. 輸入：costs = [[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。
2. 輸入：costs = [[7,6,2]]，輸出：2

提示：costs.length == n，costs[i].length == 3，1 <= n <= 100，1 <= costs[i][j] <= 20。

---

我們用動(dòng)態(tài)規(guī)劃的思想來解決這個(gè)問題。

確定狀態(tài)表示：根據(jù)經(jīng)驗(yàn)和題目要求，我們用dp[i]表示粉刷完i位置的房子后，此時(shí)的最少花費(fèi)。這可以細(xì)分為：

• 用dp[i][0]表示：將i位置的房子粉刷成紅色之后的最少花費(fèi)。
• 用dp[i][1]表示：將i位置的房子粉刷成藍(lán)色之后的最少花費(fèi)。
• 用dp[i][2]表示：將i位置的房子粉刷成綠色之后的最少花費(fèi)。

簡單來說，在dp[i][j]中，i表示最后一個(gè)粉刷的房子的編號(hào)；j表示最后一個(gè)粉刷的房子中，粉刷的顏色的編號(hào)；dp[i][j]表示此時(shí)的最少花費(fèi)。

推導(dǎo)狀態(tài)轉(zhuǎn)移方程：我們考慮最近的一步，即粉刷完i - 1位置的房子之后的情況。

• 考慮dp[i][0]。把i位置的房子粉刷成紅色，所以只能把i - 1位置的房子粉刷成藍(lán)色或者綠色。那么，把i位置的房子粉刷成紅色之后的最少花費(fèi)，就應(yīng)該是把i - 1位置的房子粉刷成藍(lán)色或者綠色之后的最少花費(fèi)，兩種情況的較小值，再加上把i位置粉刷成紅色的花費(fèi)。即dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]。
• 同理，dp[i][1] =?min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]，dp[i][2] =?min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]。

綜上所述：dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]，dp[i][1] =?min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]，dp[i][2] =?min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]。

初始化：根據(jù)狀態(tài)轉(zhuǎn)移方程，在計(jì)算dp[0][j]，其中j的范圍是[0, 2]時(shí)，會(huì)發(fā)生越界訪問，所以要進(jìn)行相應(yīng)的初始化。

• dp[0][0]表示把0位置的房子粉刷成紅色后，此時(shí)的最少花費(fèi)，顯然dp[0][0] = costs[0][0]。
• 同理dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]。

綜上所述：dp[0][0] = costs[0][0]，dp[0][1] = costs[0][1]，dp[0][2] = costs[0][2]。

當(dāng)然，我們可以在最前面添加一個(gè)輔助結(jié)點(diǎn)dp[0][j] = 0，其中j的范圍是[0, 2]。這樣，根據(jù)狀態(tài)轉(zhuǎn)移方程，以dp[i][0]為例，此時(shí)min(dp[0][1], dp[0][2]) = 0，輔助結(jié)點(diǎn)的值不影響結(jié)果，符合預(yù)期。

填表順序：根據(jù)狀態(tài)轉(zhuǎn)移方程，對(duì)于dp[i][j]只依賴于dp[i - 1][j]，j的范圍是[0, 2]。那么，我們只需要沿著i增大的方向填表。

返回值：由于不確定把最后一個(gè)房子粉刷成什么顏色，根據(jù)狀態(tài)表示，最終應(yīng)返回把最后一個(gè)房子粉刷成紅色、藍(lán)色或者綠色這3種情況中，最少花費(fèi)的最小值，即dp[n][j]的最小值，其中j的范圍是[0, 2]。

細(xì)節(jié)問題：由于新增了一個(gè)輔助結(jié)點(diǎn)，此時(shí)dp表的規(guī)模就不是n x 3，而是(n + 1) x 3。同時(shí)需注意下標(biāo)的映射關(guān)系，dp[i][j]對(duì)應(yīng)的是costs[i - 1][j]。

時(shí)間復(fù)雜度：O(N)，空間復(fù)雜度：O(N)。

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();// 創(chuàng)建dp表vector<vector<int>> dp(n + 1, vector<int>(3));// 填表for (int i = 1; i <= n; i++) {dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];}// 返回結(jié)果return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};