Simple Intiution - 3D DP || track of 2 previous || n*3*3
Code


# Code
```cpp []
class Solution {
    
    long long rec(int i , int prev1,int prev2,int n, vector<vector<int>>& cost,
    vector<vector<vector<long long>>> &dp) {
        if(i >= n/2) {
            return 0;
        }
        long long ans = LLONG_MAX;
        if(dp[i][prev1 + 1][prev2 + 1] != -1) {
            return dp[i][prev1+1][prev2 + 1];
        }
        for(int color1 = 0; color1 < 3;color1++) {
            for(int color2 = 0; color2 < 3;color2++) {
                if(color1 == color2) {
                    continue;
                }
                if(color1 == prev1 || color2 == prev2) {
                    continue;
                }
                long long minCost = cost[i][color1] + cost[n - i - 1][color2] + rec(i + 1,color1,color2,n,cost,dp);
                ans = min(ans,minCost);
            }
        }
        return dp[i][prev1+1][prev2 + 1] = ans;
    }
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<vector<vector<long long>>> dp(n,vector<vector<long long>> (4,vector<long long>(4,-1)));
        return rec(0,-1,-1,n,cost,dp);
    }
};
```
['Dynamic Programming', 'Greedy', 'Matrix', 'C++']