Leetcode refers to offer II 091 Paint house - modify in place

【LetMeFly】 The finger of the sword Offer II 091. Paint the house - Modify in place

Force button topic link ：https://leetcode.cn/problems/JEj789/

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

 

Be careful ： This topic and the main station 256  The question is the same ：https://leetcode-cn.com/problems/paint-house/

Method 1 ： Dynamic programming

This is a dynamic programming that is easy to think of , We use it $dp[i][j]$ It means the first one $i+1$ Square painting No $j$ When colors , front $i+1$ The minimum cost of a square .

that ,$mindp[n-1][0,1,2]$ That's the answer. （ The first $n$ Paint a square into $3$ One of the colors , front $n$ The minimum cost of a square ）

however , Two adjacent squares cannot have the same color . therefore The recursive formula ：

• $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]$

If modification is allowed $costs$ Array , So we can use it directly $costs$ Array instead of $dp$ Array ,$costs[i][j]+=min(costs[i-1][xx])$ that will do .

• Time complexity $O(n)$, among $n$ It's the number of houses
• Spatial complexity ：
  • If it can be modified $costs$ Array , There is no need to open up additional array space , Just use constant variables , At this time, the space complexity is $O(1)$;
  • If you can't modify $costs$ Array , that If you open an extra $dp$ Array , The space complexity is $O(n)$; If you use $3$ Variables instead of $dp$ Array , Spatial complexity $O(1)$（ because dp Array number $i-1$ The previous content will not be used again ）

AC Code

C++

class Solution {
    
public:
    int minCost(vector<vector<int>>& costs) {
    
        for (int i = 1; i < costs.size(); i++) {
    
            costs[i][0] += min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += min(costs[i - 1][0], costs[i - 1][1]);
        }
        return min(costs[costs.size() - 1][0], min(costs[costs.size() - 1][1], costs[costs.size() - 1][2]));
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125456885