'''
keys: 
Solutions:
Similar: 265
T:
S:
'''
from typing import List
from functools import lru_cache


class Solution:
     
    # dp; O(n) for T and O(1) for S; bottom up
    def minCost3(self, costs: List[List[int]]) -> int:  
        if len(costs) == 0: return 0
        for i in reversed(range(len(costs) - 1)): # starting from the last house
            # Total cost of painting i-th house red.
            costs[i][0] += min(costs[i + 1][1], costs[i + 1][2])
            # Total cost of painting i-th house green.
            costs[i][1] += min(costs[i + 1][0], costs[i + 1][2])
            # Total cost of painting i-th house blue.
            costs[i][2] += min(costs[i + 1][0], costs[i + 1][1])
    
        return min(costs[0]) # Return the minimum in the first row.
    
    
    # dp; O(n) for T and real O(1) for S; bottom up
    def minCost2(self, costs: List[List[int]]) -> int:

        if len(costs) == 0: return 0
        previous_row = costs[-1]
        for n in reversed(range(len(costs) - 1)):
    
            # PROBLEMATIC CODE IS HERE
            # This line here is NOT making a copy of the original, it's simply
            # making a reference to it Therefore, any writes into current_row
            # will also be written into "costs". This is not what we wanted!    
            current_row = costs[n]
    
            # Total cost of painting nth house red?
            current_row[0] += min(previous_row[1], previous_row[2])
            # Total cost of painting nth house green?
            current_row[1] += min(previous_row[0], previous_row[2])
            # Total cost of painting nth house blue?
            current_row[2] += min(previous_row[0], previous_row[1])
            previous_row = current_row
    
        return min(previous_row)
    
    
    # O(n) for S and T, with memo，top-down
    def minCost1(self, costs: List[List[int]]) -> int:
        
        def paint_cost(i, color): # i as house idx
            if (i, color) in memo:
                return memo[(i, color)]
            total_cost = costs[i][color]
            if i == len(costs) - 1:
                pass # skip and go straight to return
            elif color == 0:
                total_cost += min(paint_cost(i + 1, 1), paint_cost(i + 1, 2))
            elif color == 1:
                total_cost += min(paint_cost(i + 1, 0), paint_cost(i + 1, 2))
            else:
                total_cost += min(paint_cost(i + 1, 0), paint_cost(i + 1, 1))
            memo[(n, color)] = total_cost
            return total_cost
    
        if costs == []:
            return 0

        memo = {}
        return min(paint_cost(0, 0), paint_cost(0, 1), paint_cost(0, 2))

    
    # lru; O(n) for S and T, with memo
    def minCost(self, costs):
        # If maxsize is set to None, the LRU feature is disabled and the cache
        # can grow without bound.
        @lru_cache(maxsize=None)
        def paint_cost(n, color):
            total_cost = costs[n][color]
            if n == len(costs) - 1:
                pass
            elif color == 0:
                total_cost += min(paint_cost(n + 1, 1), paint_cost(n + 1, 2))
            elif color == 1:
                total_cost += min(paint_cost(n + 1, 0), paint_cost(n + 1, 2))
            else:
                total_cost += min(paint_cost(n + 1, 0), paint_cost(n + 1, 1))
            return total_cost

        if costs == []:
            return 0
        return min(paint_cost(0, 0), paint_cost(0, 1), paint_cost(0, 2))