Standard Dp problem
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:
#define ll long long
#define pb push_back
    ll dp[50001][4][4];
    ll INF = 1e18 + 1;
    ll rec(ll level, ll l, ll r, ll n, vector<vector<int>>& cost) {
        // base case
        if (level == (n / 2)) {
            return 0;
        }
        // cache check
        if (dp[level][l][r] != -1) {
            return dp[level][l][r];
        }
        // transitions
        ll ans = INF;
        for (ll i = 0; i < 3; i++) {
            if (i == l) {
                continue;
            }
            ll x = cost[level][i];
            for (ll j = 0; j < 3; j++) {
                if (j == i || j == r) {
                    continue;
                }
                x += cost[n - 1 - level][j];
                ans = min(ans, x + rec(level + 1, i, j, n, cost));
                x -= cost[n - 1 - level][j];
            }
        }
        // save and return
        return dp[level][l][r] = ans;
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        for(ll i=0;i<=(n/2);i++){
            for(ll j=0;j<=3;j++){
                for(ll k=0;k<=3;k++){
                    dp[i][j][k]=-1;
                }
            }
        }
        ll ans=rec(0,3,3,n,cost);
        return ans;
    }
};
```
['C++']