Leetcode daily question - Sword finger offer II 091 Paint the house

subject

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

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

Ideas

Typical dynamic programming problems , You can combine the costs Array as dp Array , First column 、 Second column 、 The meaning of the third column is the cost of painting the wall in this column , The state transition equation is this column plus one row and two other columns , Finally back to dp The minimum value of the last row of the array .

Answer key

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs) - 1
        for i in range(1, len(costs)):
        	#  State transition equation 
            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[n])