Straightforward dp solution, with time complexity: O(9n)
IntuitionBecause n is even, we can paint houses from the beginning and the end simultaneously, until we reach the middle.Say we paint the previous left and righ
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Because n is **even**, we can paint houses from the beginning and the end simultaneously, until we reach the middle.

Say we paint the previous left and right houses with **01** colors, then we can paint the next houses with **10, 12, 20** colors.

For each dp[i], we have six options: **01,02,10,12,20,21**, standing for colors for left house and right house. And for each option, there are three possible previous options. Therefore, there is a 2-D dp solution.
# Complexity
- Time complexity:
O(9n) 

# Code
```python3 []
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        dp = [dict() for _ in range(n // 2 + 1)]

        options = dict()
        for i in range(3):
            for j in range(3):
                if j == i:
                    continue
                k = 3 - (i + j)
                options[(i, j)] = [(j, i), (j, k), (k, i)]

        for i in range(n // 2):
            for k, v in options.items():
                dp[i + 1][k] = (
                    min(dp[i].get(x, 0) for x in v)
                    + cost[i][k[0]]
                    + cost[n - 1 - i][k[1]]
                )
        return min(dp[-1].values())
```
['Python3']