Easy and intuitive memoization
IntuitionFold the array and bring the equidistant elements together and pass on two values to the next recursive function.
The colour of this array and the colo
# Intuition
Fold the array and bring the equidistant elements together and pass on two values to the next recursive function.
The colour of this array and the colour of its equidistant array.
Then the next element will have to select it's color from everything except col1 and it's corresponding equidistant element will have to select values from everything except col2. Also col1!=col2.
Try out all the possible combinations and eliminate the impossible combinations and take the minimum from the possible combiantions.

# Complexity
- Time complexity:
O((n/2)* 4 *4) half of the indexes and 4 options for every index col1 and col2

- Space complexity:
O( n * 4 * 4 ) size of the 3-D DP array

# Code
```cpp []
class Solution {
    long long n;
    long long dp[100005][4][4];
    vector<vector<int>> cost;
private:
    long long rec( long long ind, long long col1, long long col2 ){
        if( ind >= n/2 )return 0;
        if( dp[ind][col1][col2]!=-1 )return dp[ind][col1][col2];
        long long result = 1e15;
        for(long long i=1; i<=3; i++){
            for(long long j=1; j<=3; j++){
                if( i!=col1 && j!=col2 && i!=j ){
                    result = min(result, cost[ind][i-1] + cost[n-ind-1][j-1] + rec( ind+1, i, j ));
                }
            }
        }
        return dp[ind][col1][col2] = result;
    }
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        n = cost.size();
        this->n = n;
        this->cost = cost;
        memset(dp, -1, sizeof(dp));
        long long ans = rec( 0, 0, 0 );
        return ans;
    }
};
```
['C++']