Leetcode: Sword finger offer II 091 Painting house [2D DP]

analysis

dp [i][j] It means the first one i A house is painted j Minimum cost of colors
dp[i][j] = min(dp[i - 1][jother]) + costs[i][j]

ac code

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        dp = [[0] * 3 for _ in range(n)]
        # init
        for j in range(3):
            dp[0][j] = costs[0][j]
        
        for i in range(1, n):
            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]
        
        return min(dp[-1])

summary

Simple dp