Simple recursive top-down solution. 3*3*n
Code


# Code
```cpp []
class Solution {
public:

    int midval;
    int n;
    long long dp[50000][3][3];
    long long dfs(vector<vector<int>>& cost,int indx,int head,int tail)
    {
        if(indx<0) return 0;
        if(dp[indx][head][tail]!=-1) return dp[indx][head][tail];
        long long ans=1e11;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if((i!=j&&i!=head&&j!=tail)||(indx==midval&&i!=j))
                {
                    ans=min(ans,cost[indx][i]+cost[n-indx-1][j]+dfs(cost,indx-1,i,j));
                }
            }
        }
        return dp[indx][head][tail]=ans;
    }

    long long minCost(int size, vector<vector<int>>& cost) 
    {
        n=size;
        midval=n/2-1;
        memset(dp,-1,sizeof(dp));
        return dfs(cost,midval,0,0);
    }
};
```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']