Easy C++ memoized Solution.
IntuitionIn this question for the very first house we have three options to color it , but as we move further our options start decresing as we have two contrai
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
In this question for the very first house we have three options to color it , but as we move further our options start decresing as we have two contraints like adjancent house cannot have the same color and equidistant houses from the end should not have the same color.

So as we have choices for every house , we can give try to all of them and pick the minimum cost out of that.we can use recursion to try all possible cases and memoized it.

# Approach
<!-- Describe your approach to solving the problem. -->
So fisrt thing is that we need to traverse only half of the array , because along with painting the starting housed we will also paint there equidistant houses.

So to mainitain equidistant value of every index we can use hashmap.

Then in our recursive call we have three parameter one is for index ,second is for color of the left adjacent element and third is for storing the color of the right adjacent element.

At every index with the help of for loop we can try to color the houses with every possible pattern, and try to minimize our answer.

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


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

# Code
```cpp []
class Solution {
public:
unordered_map<int,int> equMap;
    long long dp[100005][4][4];
    long long solve(int idx,int prev,int nex,vector<vector<int>>&cost,int n)
    {
        if(idx>=n/2)return 0;
        long long ans=1e15;
        if(dp[idx][prev][nex]!=-1)return dp[idx][prev][nex];
        if(idx==0)
        {
            for(int col=1;col<=3;col++)
            {
                long long val=0;
                for(int sec=1;sec<=3;sec++)
                {
                    if(sec==col)continue;
                    val=cost[0][col-1]+cost[equMap[0]][sec-1]+solve(idx+1,col,sec,cost,n);
                    ans=min(ans,val);
                }
            }
        }
        else
        {
            for(int col=1;col<=3;col++)
            {
                if(col==prev)continue;
                for(int sec=1;sec<=3;sec++)
                {
                    if(sec==nex or col==sec)continue;
                    long long val=cost[idx][col-1]+cost[equMap[idx]][sec-1]+solve(idx+1,col,sec,cost,n);
                    ans=min(ans,val);
                }
            }
        }
        return dp[idx][prev][nex]=ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        //hk
        memset(dp,-1,sizeof(dp));
        int i=0;
        int j=n-1;
        while(i<j)
        {
            equMap[i]=j;
            i++;
            j--;
        }
        long long ans=solve(0,0,0,cost,n);
        return ans;




    }
};
```
['C++']