265. Paint House II

main.py

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        
        
        # Recursion or top-down approach
        # state: at any given state returns the minimum cost of painting a house i
        #    with color k which is: costs[i][k] + minimum cost of painting a house i + 1 with not k
        
        # state variables are: 
        # i house index
        
        # k color for second house
        
        # recurrence relation: dp(i, k) = costs[i][k] + min(dp(i+1))
        # base case if i == len(costs) return 0
        
        @lru_cache(None)
        def dp(i, k):
            if i == len(costs):
                return 0
            
            
            c = costs[i][k] + min([dp(i+1, color) for color, _ in enumerate(costs[i]) if color != k])
            return c
        
        return min([dp(0, color) for color, _ in enumerate(costs[0])])