BEST SOLUTION EVER C++ 
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
class Solution {
public:
    long long solveUsingRec(vector<vector<int>>& cost,int n,int prev1,int prev2, int index){
        //Base Condition
        if(index>=n/2){
            return 0;
        }
        long long ans1=LLONG_MAX;
        long long travLastIndex=n-index-1;
        if(index==0){
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i!=j){
                        long long temp=cost[index][i]+cost[travLastIndex][j]+solveUsingRec(cost,n,i,j,index+1);
                        ans1=min(ans1,temp);
                    }
                }
            }
        }
        else{
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i!=j && i!=prev1 && j!=prev2){
                        long long temp=cost[index][i]+cost[travLastIndex][j]+solveUsingRec(cost,n,i,j,index+1);
                        ans1=min(ans1,temp);
                    }
                }
            }
        }
        return ans1;
    }

    long long solveUsingMem(vector<vector<int>>& cost,int n,int prev1,int prev2, int index,vector<vector<vector<long long >>> &dp){
        //Base Condition
        if(index>=n/2){
            return 0;
        }
        if(dp[prev1][prev2][index]!=-1)
            return dp[prev1][prev2][index];

        long long ans1=LLONG_MAX;
        long long travLastIndex=n-index-1;
        if(index==0){
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i!=j){
                        long long temp=cost[index][i]+cost[travLastIndex][j]+solveUsingMem(cost,n,i,j,index+1,dp);
                        ans1=min(ans1,temp);
                    }
                }
            }
        }
        else{
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i!=j && i!=prev1 && j!=prev2){
                        long long temp=cost[index][i]+cost[travLastIndex][j]+solveUsingMem(cost,n,i,j,index+1,dp);
                        ans1=min(ans1,temp);
                    }
                }
            }
        }
        dp[prev1][prev2][index]=ans1;
        return ans1;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        int prev1=0;
        int prev2=0;
        int index=0;
        // return solveUsingRec(cost,n,prev1,prev2,index);

        vector<vector<vector<long long>>>dp(4,vector<vector<long long>>(4,vector<long long>(cost.size()+1,-1)));
        return solveUsingMem(cost,n,prev1,prev2,index,dp);
        
    }
};
```
['Dynamic Programming', 'Recursion', 'C++']