top down- dp (memo)
IntuitionApproachComplexity
Time complexity:
O(n * 3 * 3)
Space complexity:
O(n * 3 * 3)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)$$ -->
O(n * 3 * 3)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n * 3 * 3)
# Code
```cpp []
class Solution {
public:
    long long dp[100003][5][5];
    long long solve(int i, int front_prev, int back_prev, int n, vector<vector<int>> &cost){
        if(i >= n/2 )return 0LL;
        if(dp[i][front_prev+1][back_prev+1] != -1LL)return dp[i][front_prev+1][back_prev+1];
        
        
        long long res = 1e12;
        
        for(int front =0; front < 3; front++){
            if(front_prev == front)continue;
            for(int back =0; back < 3; back++){
                if(front != back && back_prev != back){
                // cout << i <<" "<< front <<" " << back << endl;
                res = min(res, (long long)(cost[i][front] + cost[n-i-1][back] + solve(i+1, front, back,n,cost))); 
            }
        }
        }
        return dp[i][front_prev+1][back_prev+1] = res;
        
    }
    long long minCost(int n, vector<vector<int>>& cost) {
        memset(dp, -1LL, sizeof(dp));
        long long ans = 0;
        return solve(0, -1, -1, n, cost);
    }
};
```
['Dynamic Programming', 'Memoization', 'C++']