Top-down dp
Typical paint house DP. If you've seen parts 1-3, this should not be a big deal for you.A bit tricky, but douable:DP rules on an example:color of 2 can't be the
Typical paint house DP. If you've seen parts 1-3, this should not be a big deal for you.

A bit tricky, but douable:

DP rules on an example:
```
1 2 3 4
```
color of 2 can't be the same as 1 # rule 1
color of 3 can't be the same as 4 # rule 1
color of 1 can't be the same as 4 # rule 2
color of 2 can't be the same as 3 # rule 2

you must pick 2 colors for left and right that:
- left_color != left_prev_color and right_color != right_prev_color (rule #1)
- left_color != right_color (rule #2)


```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        @cache
        def dfs(i, prev_left_col, prev_right_col):
            if i == N // 2:
                return 0
            res = inf
            for l in range(3):
                for r in range(3):
                    if l != prev_left_col and r != prev_right_col and l != r:
                        res = min(res, cost[i][l] + cost[~i][r] + dfs(i + 1, l, r))
            return res            
        N = len(cost)
        return dfs(0, -1, -1)
```
['Dynamic Programming', 'Python3']