Recursion with Memoization 
IntuitionGiven the constraints about equidistant houses cannot have same color, the intuition is that we'll need to keep track of the state of the houses that a
# Intuition
Given the constraints about equidistant houses cannot have same color, the intuition is that we'll need to keep track of the state of the houses that are equidistant from both ends when building up the solution.

# Approach
Build a function helper(i, j, k, l) that returns the min cost if starting at index i with color k, and ending at index j with color l. 

We use recursion to define this function. The base case is that i == j - 1: if k == l, we know this will violate the constraint and we can assign infinity cost to it (i.e., not valid solution); if k != l, we know the cost is cost[i][k] + cost[j][l]. 

# Complexity
- Time complexity:
O(n). Because i + j == n - 1, and we have 3 (constant number) of colors 


- Space complexity:
O(n), needed for memoization and recursion stack.

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        
        # there is a total of 3 colors
        n = len(cost) # number of houses

        memo = dict()
        # minimum cost if starting at index i with color k, and ending at index j with color l
        def helper(i, j, k, l):
            if (i, j, k, l) in memo:
                return memo[(i, j, k, l)]
            
            if i == j - 1:
                if k == l:
                    result = float('inf') # cannot do this
                else:
                    result = cost[i][k] + cost[j][l]
            else:
                # i < j - 1, need to move closer towards each other
                if k == l:
                    result = float('inf')
                else:
                    # need to choose a color for i + 1, and a color for j - 1
                    result = float('inf')
                    for temp_color_1 in range(3):
                        for temp_color_2 in range(3):
                            if temp_color_1 == k or temp_color_2 == l:
                                # cannot be the same with its neighbor
                                continue
                            elif temp_color_1 == temp_color_2:
                                # cannot be the same with house equidistant
                                continue
                            else:
                                result = min(result, cost[i][k] + cost[j][l] + helper(i+1, j-1, temp_color_1, temp_color_2))
            memo[(i,j,k,l)] = result
            return result
        
        # different ways to start
        out = float('inf')
        for start_color in range(3):
            for end_color in range(3):
                out = min(out, helper(0, n-1, start_color, end_color))
        return out
                
        




```
['Python3']