256. Paint House

256. Paint House

 

내 풀이 (맞춤)

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        dp = [[0]*3 for _ in range(n)]

        dp[-1][:] = costs[-1][:]        

        if n > 1:
            for r in range(n-1-1, -1, -1):
                for c in range(3):
                    dp[r][c%3] = min(dp[r+1][(c+1)%3], dp[r+1][(c+2)%3]) + costs[r][c%3]

        #print(dp)
        return min(dp[0][:])

 

좀더 최적화

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0:
            return 0

        # dp 배열 초기화 (마지막 집은 그대로)
        dp = costs[:]   

        if n > 1:
            for r in range(n-1-1, -1, -1):
                for c in range(3):
                    dp[r][c%3] += min(dp[r+1][(c+1)%3], dp[r+1][(c+2)%3])

        return min(dp[0][:])

 

if n > 1: 빼도 됨. 

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0:
            return 0

        # dp 배열 초기화 (마지막 집은 그대로)
        dp = costs[:]   

        #if n > 1:
        for r in range(n-1-1, -1, -1):
            for c in range(3):
                dp[r][c%3] += min(dp[r+1][(c+1)%3], dp[r+1][(c+2)%3])

        return min(dp[0][:])

 

 

https://youtu.be/-w67-4tnH5U?si=gi3vrTB6dm8opd1r