力扣原題鏈接，點擊跳轉。

假設有n個房子，每個房子可以粉刷成紅色、藍色或者綠色。相鄰2個房子不能刷同一種顏色。下標為i的房子粉刷成下標為j的顏色的價格是costs[i][j]。至少需要花多少錢？

我們用動態規劃的思想來解決這個問題。首先定義狀態表示。用dp[i][j]表示刷到下標為i的房子時，下標為i的房子刷成下標為j的顏色，此時至少需要花多少錢。接著推導狀態轉移方程。以dp[i][0]為例，假設紅色、藍色和綠色的下標分別為0、1和2，那么dp[i][0]說明下標為i的房子刷成了紅色，下標為i-1的房子刷成了藍色或者綠色，所以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]。

初始化時，可以在最前面加一個虛擬節點，虛擬節點都初始化為0，這是為了使得當i=1時，min(dp[i-1][j],dp[i-1][k])=0，從而不影響計算結果。至于填表順序，應從左往右填表，每次都把三種顏色的位置都填了。注意到加了一個虛擬節點后，dp表中的i對應的是costs表中的i-1，最終應返回min(dp[n][0],dp[n][1],dp[n][2])，對應costs表中的n-1。

class Solution
{
public:int minCost(vector<vector<int>>& costs){// 創建dp表int n = costs.size();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];}return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};