100% faster solution using 3D DP
IntuitionApproachComplexity
Time complexity:
O(n*4*4)

Space complexity:
O(n*4*4)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

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

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

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

# Code
```cpp []
class Solution {
public:
    int N;
    long long minCost(int n, vector<vector<int>>& cost,int col1, int col2, vector<vector<vector<long long>>>& dp) {
        // base test case
        if(n==N/2){
            return 0;
        }
        // general condition
        if(dp[n][col1][col2]!=-1) return dp[n][col1][col2];

        long long ans = LLONG_MAX;

         for(int j=1;j<4;j++){
            if(col2!=j){
                for(int k=1;k<4;k++){
                    if(col1!=k){
                        if(j!=k){
                           ans= min(ans,minCost(n-1, cost, k, j, dp)+cost[n-1][j-1]+cost[N-n][k-1]);
                        }
                    }
                }
            }
         }
         return dp[n][col1][col2]=ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        this->N= n;
        vector<vector<vector<long long>>> dp(n+1, vector<vector<long long>>(4, vector<long long>(4,-1)));
        return minCost(n, cost, 0, 0, dp);
    }
};
```
['C++']