Top down DP
IntuitionHonestly got lucky with a hunch I had and it workedThe problem statement reminded me of a DP problemHow I went about solving the problemlet a, b, c be
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Honestly got lucky with a hunch I had and it worked

The problem statement reminded me of a DP problem
# How I went about solving the problem
let a, b, c be the three colors the houses can take on taking on the indices 0, 1, 2 respectively
1) Try to figure out how to get mincost if you didnt have the equidistant restriction
- min(a + dp(i + 1, a) if prev != a ... for b and c)
2) Try to figure out how to integrate the equidistant constraint
- assign colors for house at idx i and n - i in one call of dp
- let a1, b1, c1 be the cost for house at i 
- let a2, b2, c3 be cost for house at n - i
- answer is min(a1 + b2 + dp(i + 1, 0, 1) ... repeat all combos of colors for house at i and n - i respectively up to idx n // 2) dont forget to obey the adjacent color rule


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(N)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(N)

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        # 3 colors for the houses

        @cache
        # kinda like two pointer dp
        # prev is prior to i
        # otherPrev is after n - i
        # a, b, c -> 0, 1, 2
        def dp(i, prev, otherPrev):
            if i >= n // 2: return 0
            a1, b1, c1 = cost[i]
            a2, b2, c2 = cost[n - i - 1]

            res = inf
            if prev != 0: # pick a
                if otherPrev != 1:
                    res = min(res, a1 + b2 + dp(i + 1, 0, 1))
                if otherPrev != 2:
                    res = min(res, a1 + c2 + dp(i + 1, 0, 2))

            if prev != 1: # pick b
                if otherPrev != 0:
                    res = min(res, b1 + a2 + dp(i + 1, 1, 0))
                if otherPrev != 2:
                    res = min(res, b1 + c2 + dp(i + 1, 1, 2))

            if prev != 2: # pick c
                if otherPrev != 1:
                    res = min(res, c1 + b2 + dp(i + 1, 2, 1))
                if otherPrev != 0:
                    res = min(res, c1 + a2 + dp(i + 1, 2, 0))

            return res
            
            

        return dp(0, -1, - 1)
            
```
['Python3']