Python Simple Top-Down DP
Approach
DP states/variables: left pointer, right pointer, previous left color, previous right color
Base case: If i > j, return 0.
Transition: Try all valid co
# Approach
<!-- Describe your approach to solving the problem. -->
- DP states/variables: left pointer, right pointer, previous left color, previous right color
- Base case: If i > j, return 0.
- Transition: Try all valid color combinations for i and j, ensuring no consecutive colors match.


# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        
        @cache
        def dp(i, prev_i_color, j, prev_j_color):
            if i > j:
                return 0
            res = float("inf")
            # Color 0 on i
            if prev_i_color != 0:
                # Color 1 on j
                if prev_j_color != 1:
                    res = min(res, cost[i][0] + cost[j][1] + dp(i + 1, 0, j - 1, 1))
                # Color 2 on j
                if prev_j_color != 2:
                    res = min(res, cost[i][0] + cost[j][2] + dp(i + 1, 0, j - 1, 2))
            # Color 1 on i
            if prev_i_color != 1:
                # Color 0 on j
                if prev_j_color != 0:
                    res = min(res, cost[i][1] + cost[j][0] + dp(i + 1, 1, j - 1, 0))
                # Color 2 on j
                if prev_j_color != 2:
                    res = min(res, cost[i][1] + cost[j][2] + dp(i + 1, 1, j - 1, 2))
            # Color 2 on i
            if prev_i_color != 2:
                # Color 0 on j
                if prev_j_color != 0:
                    res = min(res, cost[i][2] + cost[j][0] + dp(i + 1, 2, j - 1, 0))
                # Color 1 on j
                if prev_j_color != 1:
                    res = min(res, cost[i][2] + cost[j][1] + dp(i + 1, 2, j - 1, 1))
            return res
            
        res = dp(0, -1, n - 1, -1)
        dp.cache_clear()
        return res
```
['Dynamic Programming', 'Python3']