Memoised DP code
IntuitionThis is a DP problem since we have to find the minimum cost out of all possible ways that the houses can be colored respecting the given conditions.App
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

This is a DP problem since we have to find the minimum cost out of all possible ways that the houses can be colored respecting the given conditions.

# Approach
<!-- Describe your approach to solving the problem. -->
Idea is to keep track of the last color we chose to paint the house and not take the same color again for an adjacent house. 

Also , since two houses which are equidistant from the starting and end cannot have same color, we need to consider the ith house and (n-1-i)th house together.

All we need to do now is to first pick a color for the ith house which shouldnt be the same as the color of the (i-1)t house . Now after we have choosen the color for the ith house , we will try to choose the color for (n-1-i)th house , which shouldnt be the same as the color choosen for the ith house as well as the color choosen for (n-i)th house.


# Code
```cpp []
class Solution {
public:
    typedef long long ll;
int n;
ll dp[100000+5][6][6];
    ll f(int i,int prev1,int prev2,vector<vector<int>>& cost){
        if(i == cost.size()/2) return 0;
        if(dp[i][prev1+1][prev2+1]!=-1) return dp[i][prev1+1][prev2+1];
        ll har=LLONG_MAX;ll mini=LLONG_MAX;
        for(int j=0;j<3;j++){
            if(j!=prev1){
                //first = cost[i][j]+f(i+1,j,prev2,cost);
                for(int k=0;k<3;k++){
                    if(k!=prev2 and k!=j){
                        har=cost[i][j]+cost[n-1-i][k]+f(i+1,j,k,cost);
                        mini=min(mini,har);
                    }
                }
            }
        }
        return dp[i][prev1+1][prev2+1]=mini;
        
    }
    long long minCost(int sar, vector<vector<int>>& cost) {
        n=sar;
        memset(dp,-1,sizeof(dp));
        return f(0,-1,-1,cost);
    }
};
```
['Dynamic Programming', 'C++']