Dynamic programming
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:
    long long minCost(int n, vector<vector<int>>& cost) {
        vector<vector<vector<long long>>> dp(n/2 , vector<vector<long long>>(3 , vector<long long>(3 , LONG_MAX)));
        for(int j = 0 ; j < 3 ; j++){
            for(int k = 0 ; k < 3 ; k++){
                if(j != k){
                    dp[0][j][k] = cost[0][j] + cost[n-1][k];
                }
            }
        }
        long long ans = LONG_MAX;
        for(int i = 1 ; i < n/2 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                for(int k = 0 ; k < 3 ; k++){
                    if(j != k){
                        for(int l = 0 ; l < 3 ; l++){
                            for(int m = 0 ; m < 3 ; m++){
                                if(l != m){
                                    if(l != j && m != k){
                                        dp[i][j][k] = min(dp[i][j][k] ,cost[i][j] + cost[n-1-i][k] + dp[i-1][l][m]);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i = 0 ; i < 3 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                if(i != j)ans = min(ans , dp.back()[i][j]);
            }
        }
        return ans;
    }
};
```
['C++']