Python describe LeetCode The finger of the sword Offer II 091. Paint the house

Hello everyone , I'm Qi Guanjie （qí guān jié ）, stay 【 Qi Guanjie 】 official account 、CSDN、GitHub、B Share some technical blog posts on the website and other platforms , It mainly includes front-end development 、python The backend development 、 Applet development 、 Data structure and algorithm 、docker、Linux Common operation and maintenance 、NLP And other related technical blog , Time flies , Future period , come on. ~

If you love bloggers, you can focus on the bloggers' official account. 【 Qi Guanjie 】(qí guān jié), The articles inside are more complete and updated faster . If you need to find a blogger, you can leave a message at the official account. , I will reply to the message as soon as possible .

---

This article was originally written as 【 Qi Guanjie 】（qí guān jié ）, Please support the original , Some platforms have been stealing blog articles maliciously ！！！ All articles please pay attention to WeChat official account 【 Qi Guanjie 】.

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 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/

Python describe

Dynamic programming .

dp[i][j] Express 0~i Houses and i-1 The first i Use a house j The lowest cost of color
be dp[i][j] = min(dp[i-1][(j-1)%3] , dp[i-1][(j+1)%3]) + costs[i][j]

class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
dp = [[2**32 for j in range(3)] for i in range(n)]
for i in range(3):
dp[0][i] = costs[0][i]
for i in range(1,n):
for j in range(3):
dp[i][j] = min(dp[i-1][(j-1)%3] , dp[i-1][(j+1)%3]) + costs[i][j]
return min(dp[n-1])