[Jianzhi offer II 091. painting the house]

source ： Power button （LeetCode）

describe ：

If there is a row of houses , common n individual , Every house can be painted red 、 One of the three colors blue or green , You need to paint all the houses and make the two adjacent houses not the same color .

Of course , Because the prices of different colors of paint on the market are different , So the cost of painting the house in different colors is different . The cost of painting each house in a different color is one n x 3 Positive integer matrix of costs To represent the .

for example ,costs[0][0] It means the first one 0 The cost of painting the house red ;costs[1][2] It means the first one 1 The cost of painting the house green , And so on .

Please calculate the minimum cost of painting all the houses .

Example 1：

 Input : costs = [[17,2,17],[16,16,5],[14,3,19]]
 Output : 10
 explain :  take  0  No. 1 house painted blue ,1  No. 1 house painted green ,2  No. 1 house painted blue .
      Minimum cost : 2 + 5 + 3 = 10.

Example 2：

 Input : costs = [[7,6,2]]
 Output : 2

Tips :

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

Method ： Dynamic programming

Code ：

class Solution {
    
public:
    int minCost(vector<vector<int>>& costs) {
    
        int n = costs.size();
        vector<int> dp(3);
        for (int j = 0; j < 3; j++) {
    
            dp[j] = costs[0][j];
        }
        for (int i = 1; i < n; i++) {
    
            vector<int> dpNew(3);
            for (int j = 0; j < 3; j++) {
    
                dpNew[j] = min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
            }
            dp = dpNew;
        }
        return *min_element(dp.begin(), dp.end());
    }   
};

Execution time ：4 ms, In all C++ Defeated in submission 96.45% Users of
Memory consumption ：9.5 MB, In all C++ Defeated in submission 56.50% Users of
author：LeetCode-Solution