Memoization Solution
IntuitionWe can solve using memoization by coloring ith house and n-i-1th house simultaneously. Hence we maintain 3 states:
index i
color of i-1 th house : left
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We can solve using memoization by coloring ```i```th house and ```n-i-1```th house simultaneously. Hence we maintain 3 states: 
1. index ```i```
2. color of i-1 th house : ```left``` 
3. color of i+1 th house: ```right```

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

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

# Code
```cpp []
class Solution {
    long long f(int i, int left, int right, int n, vector<vector<int>>& cost, vector<vector<vector<long long>>>& dp) {
        
        if(i >= n/2) return 0;
        if(dp[i][left][right]!=-1) return dp[i][left][right];

        long long t = LONG_MAX;
        for(int col1=0; col1<3; col1++) {
            if(col1 != left) {
                for(int col2=0; col2<3; col2++){
                    if((col2 != right) && (col2 != col1)) {
                        long long q = cost[i][col1] + cost[n-1-i][col2] + f(i+1, col1, col2, n, cost, dp);
                        t = min(t, q);
                    }
                }
            }
        }
        return dp[i][left][right] = t;
    }
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(4, vector<long long>(4, -1)));
        return f(0, 3, 3, n, cost, dp);
    }
};
```
``` Java []
class Solution {
    private long f(int i, int left, int right, int n, int[][] cost, long[][][] dp) {
        
        if(i >= n / 2) return 0;
        if(dp[i][left][right] != -1) return dp[i][left][right];

        long t = Long.MAX_VALUE;
        for(int col1 = 0; col1 < 3; col1++) {
            if(col1 != left) {
                for(int col2 = 0; col2 < 3; col2++) {
                    if(col2 != right && col2 != col1) {
                        long q = cost[i][col1] + cost[n - 1 - i][col2] + f(i + 1, col1, col2, n, cost, dp);
                        t = Math.min(t, q);
                    }
                }
            }
        }
        dp[i][left][right] = t;
        return t;
    }

    public long minCost(int n, int[][] cost) {
        long[][][] dp = new long[n][4][4];
        for (long[][] arr : dp) {
            for (long[] subArr : arr) {
                Arrays.fill(subArr, -1);
            }
        }
        return f(0, 3, 3, n, cost, dp);
    }
}

```

['Dynamic Programming', 'Memoization', 'C++', 'Java']