DP. Time O(n), space O(1). 7 lines
Time O(n), space O(n):Time O(n), space O(1):
 ```
Transition table:      
   dp[i+1] |    dp[i]
  dp1 [01] | [10] [12] [20]  <- selected color for house [left right]
  dp2 [02] | [10] [20] [21]     (left[i+1] != left[i])
                                (right[i+1] != right[i])
  dp1 [12] | [01] [20] [21]     (left[i] != right[i])
  dp2 [10] | [01] [02] [21]

  dp1 [20] | [02] [01] [12]
  dp2 [21] | [02] [10] [12] 
```
Time $O(n)$, space $O(n)$:
```
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        dp1, dp2 = [[0]*3 for _ in range(n//2+1)], [[0]*3 for _ in range(n//2+1)]
        for i in range(n//2):
            for j in range(3):
                j1, j2 = (j+1)%3, (j+2)%3
                dp1[i+1][j] = cost[i][j] + cost[~i][j1] + min(dp1[i][j1], dp1[i][j2], dp2[i][j1])
                dp2[i+1][j] = cost[i][j] + cost[~i][j2] + min(dp1[i][j2], dp2[i][j1], dp2[i][j2])
        return min(dp1[-1] + dp2[-1])                                                      
```
Time $O(n)$, space $O(1)$:
```
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        dp1, dp2 = [0]*3, [0]*3
        for cost_left, cost_right in zip(cost[:n//2], cost[:n//2-1:-1]):
            new_dp1, new_dp2 = [], []
            for i in range(3):
                i1, i2 = (i+1)%3, (i+2)%3
                new_dp1.append(cost_left[i] + cost_right[i1] + min(dp1[i1], dp1[i2], dp2[i1]))
                new_dp2.append(cost_left[i] + cost_right[i2] + min(dp1[i2], dp2[i1], dp2[i2]))
            dp1, dp2 = new_dp1, new_dp2
        return min(dp1 + dp2)
```
['Dynamic Programming', 'Python3']