DP Memoized Solution with Proper Comments - Easy To Understand.
IntuitionThis problem can be easily solved by considering all the combination of painting adjacent house and mirror house. But, since the n is large we have to
# Intuition
This problem can be easily solved by considering all the combination of painting adjacent house and mirror house. But, since the n is large we have to consider O(n) solution. As there can be duplicate states in the recursion, we can memoize it by storing the ans.

# Approach
Let's paint two houses at the same time, ith house and (n-i-1)th house at a time with different color.
We will have total of 9 combinations to paint both house, as there are 3 choices to paint wach house.
Suppose we are on a ith house and we will be painting ith house and (n-i-1)th house, then we want to know the color of (i-1)th house and the colour of(n-i)th house so that we don't color the adjacent houses with the same color.
Hence, we will be creating a dp of size dp[n/2+1][4][4], since we will be having 3 states(houseNumber, prevColor, prevMirrorColor)

# Complexity
- Time complexity:
It will be O(3x3xn). i.e. O(9n).

- Space complexity:
It will be O(4x4xn/2) i.e O(8n).

# Code
```cpp []
class Solution {
public:
    long long helper(vector<vector<vector<long long>>>& dp, vector<vector<int>>& cost, int prevColor, int prevMirrorColor, int currHouse, int n){
        if(currHouse >= n/2){
            // we have already painted all the houses
            return 0;
        }

        // if the currHouse is already explored with same states of color, then we already have the minimum cost stored int the dp and hence we can return the same amount without recalculating it.
        if(dp[currHouse][prevColor][prevMirrorColor] != -1){
            return dp[currHouse][prevColor][prevMirrorColor];
        }

        long long minimumCost = LLONG_MAX;
        // let i be the color of currHouse and j be the color of the (n-currHouse-1)
        for(int i = 0; i < 3; i++){
            // We will only paint the currHouse with ith color, if the color of prev house is not same.
            if(i != prevColor){
                for(int j = 0; j < 3; j++){
                    // The mirror house will only be painted if it's color is not same as it's adjacent house i.e. prevMirrorColor and it's color is not same as currHouse color
                    if(i != j && j != prevMirrorColor){
                        // Adding the cost of painting currHouse with i color and painting (n-currHouse-1) with jth color
                        long long currCost = (long long)cost[currHouse][i] + cost[n-currHouse-1][j] + helper(dp, cost, i, j, currHouse+1, n);
                        // Taking the minimum cost of all combinations
                        minimumCost = min(minimumCost, currCost); 
                    }
                }
            }
        }
        // Storing the current state in the dp to avoid recalculation of the same value.
        return dp[currHouse][prevColor][prevMirrorColor] = minimumCost;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        // We are taking a 3-D vector as dp, Since we will be having 3 states.
        // Suppose we are on a ith house and we will be painting ith house and (n-i-1)th house, then we want to know the color of (i-1)th house and the colour of(n-i)th house. So that we don't color the adjacent houses with the same color.
        // So, three states would be ith house, color of (i-1)th house and color of (n-i)th house.
        vector<vector<vector<long long>>> dp(n/2+1, vector<vector<long long>>(4, vector<long long>(4, -1)));
        return helper(dp, cost, 3, 3, 0, n);
    }
};
```
['Dynamic Programming', 'Memoization', 'C++']