MCM | Top down C++
\nclass Solution {\npublic:\n    int t[505][505];\n    \n    int solve(vector<int>& a, int i, int j){\n        if(i>j)\n            return 0;\n        if(t[i][j
```\nclass Solution {\npublic:\n    int t[505][505];\n    \n    int solve(vector<int>& a, int i, int j){\n        if(i>j)\n            return 0;\n        if(t[i][j]!=-1)\n            return t[i][j];\n        int ans=0;\n        for(int k=i;k<=j;k++){\n            int t=solve(a,i,k-1) + solve(a,k+1,j) + a[i-1]*a[k]*a[j+1];\n            ans=max(ans,t);\n        }\n        return t[i][j]=ans;\n    }\n    \n    \n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);  \n        int n=nums.size();\n        memset(t,-1,sizeof(t));\n        return solve(nums, 1, n-2);\n    }\n};\n```
[]