Easy Optimized Soln 
Intution
Use DP
While recusrsion use index from 0 to n/2, it will give two pointers once from left side and another from right side. It means we are visiting eq
# Intution
<!-- Describe your approach to solving the problem. -->
1. Use DP
2. While recusrsion use index from 0 to n/2, it will give two pointers once from left side and another from right side. It means we are visiting equdistant houses from left and right simultaneously to achieve our goal.
3. Again while calling function we are also sending the current house color for both(left and right) one, so that for the next of left house and prev of right house it will be easy to pick colors as per constarint.
4. Take minimum all possible combinations and use 3d dp to rmeber your answer.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n*k*k)+O(n/2*k*k)$$ 
=> first one is for intializing the 3d dp and second for recursion

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n*k)+O(n/2)$$
=> first one for 3d dp and second for recursion stack

# Code
```cpp []
class Solution {
public:
    long long f(int i, int prev, int next, vector<vector<int>>& cost, int n, vector<vector<vector<long long>>>& dp){
        if(i == n/2){
            return 0;
        }
        if(dp[i][prev+1][next+1] != -1) return dp[i][prev+1][next+1];
        long long minm = 1e16;
        for(int j = 0; j <= 2; j++){
            if(j == prev) continue;
            for(int k = 0; k <= 2; k++){
                if(j == k || k == next) continue;
                long long c = cost[i][j] + cost[n-1-i][k] + f(i+1, j, k, cost, n, dp);
                if(c < minm) minm = c;
            }
        }
        return dp[i][prev+1][next+1] = minm;
    } 
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<vector<vector<long long>>>dp(n+1, vector<vector<long long>>(4, vector<long long>(4, -1)));
        return f(0, -1, -1, cost, n, dp);
    }
};
```
['Array', 'Dynamic Programming', 'Memoization', 'C++']