Recursion + Memoization | clean and concise
The idea is to start from middle and expand while maintaing the beautyCode
The idea is to start from middle and expand while maintaing the beauty

# Code
```cpp []
class Solution {
    long long solve(const int i, const int j, const int prevIColor,
                    const int prevJColor, const vector<vector<int>>& cost,
                    const int red, vector<vector<vector<long long>>>& dp) {
        if (i < 0) {
            return 0;
        }

        // adding 1 to handle -1 case when we can choose from any color
        if (dp[i][prevIColor + 1][prevJColor + 1] != -1)
            return dp[i][prevIColor + 1][prevJColor + 1];

        long long lmin = LONG_MAX, temp;
        for (int fcolor = 0; fcolor < 3; ++fcolor) {
            for (int lcolor = 0; lcolor < 3; ++lcolor) {
                // check for prev color and current now same
                if (fcolor != prevIColor && lcolor != prevJColor &&
                    fcolor != lcolor) {
                    temp = solve(i - 1, j + 1, fcolor, lcolor, cost, red, dp);
                    // handled overflows 
                    if (temp != LONG_MAX) {
                        lmin =
                            min(lmin, cost[i][fcolor] + cost[j][lcolor] + temp);
                    }
                }
            }
        }

        return dp[i][prevIColor + 1][prevJColor + 1] = lmin;
    }

public:
    long long minCost(int n, vector<vector<int>>& cost) {
        int mid = n / 2 - 1;
        vector<vector<vector<long long>>> dp(
            mid + 1,
            (vector<vector<long long>>(4, (vector<long long>(4, -1)))));

        return solve(mid, mid + 1, -1, -1, cost, mid + 1, dp);
    }
};
```
['C++']