256. Paint House

main.py

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        
        # recursion
        # state is the current house we are painting with color c that has a cost + min of prev min
        # state variables are i, c
        # recurrence relation : dp(i, c) = cost[c] + min(dp(i + 1, c-1), dp(i + 1, c+1))
        # base case: i == len(costs) return 0
#         @lru_cache(None)
#         def dp(i, c):
#             if i == len(costs):
#                 return 0
            
#             colors = [index for index, d in enumerate(costs[i]) if index != c]
            
#             return costs[i][c] + min(dp(i+1, colors[0]), dp(i+1, colors[1]))
        
#         return min(dp(0, 0), dp(0, 1), dp(0, 2))
    
        # iterative
#         dp = [[0] * (len(costs[0])) for _ in range(len(costs) + 1)]
        
#         for i in range(1, len(costs) + 1):
#             for c, _ in enumerate(costs[i-1]):
#                 colors = [index for index, d in enumerate(costs[i-1]) if index != c]
#                 dp[i][c] = costs[i-1][c] + min(dp[i-1][colors[0]], dp[i-1][colors[1]])
            
#         return min(dp[len(costs)])

        # iterative with state reduction
    
        prev = [0] * 3
        for now in costs:
            prev = [now[i] + min(prev[:i]+prev[i+1:]) for i in range(3)]
        return min(prev)