Memoization
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        @cache
        def getMinCost(i, prevPaint, prevPaintEqui):
            if i >= n//2:
                return 0
            
            minCost = float('inf')
            for curPaint in range(3):
                for curPaintEqui in range(3):
                    if (curPaint == curPaintEqui or
                        curPaint == prevPaint or
                        curPaintEqui == prevPaintEqui):
                        continue
                    
                    minCost = min(
                        minCost,
                        getMinCost(i+1, curPaint, curPaintEqui) + cost[i][curPaint] + cost[n-i-1][curPaintEqui]
                    )
            
            return minCost
        
        return getMinCost(0, -1, -1)
        
```
['Memoization', 'Python3']