C++ RECURSION + MEMOIZATION
```\nclass Solution {\npublic:  \n    int dp[504][504];\n    int solve(vector&a, int i , int j)\n    {\n        // base case\n        // start from  1 to n-2\n 
```\nclass Solution {\npublic:  \n    int dp[504][504];\n    int solve(vector<int>&a, int i , int j)\n    {\n        // base case\n        // start from  1 to n-2\n        if(dp[i][j] != -1)\n            return dp[i][j];\n        int ans = 0;\n        for(int k = i+1; k <= j-1 ; k++)\n            ans = max(ans , (solve(a,i,k) + solve(a,k,j) + a[i]*a[k]*a[j])) ;\n        dp[i][j] = ans;\n        return ans;\n    }\n    int maxCoins(vector<int>& a) {\n       \n        // insert 1 at the begining and at the end\n        a.insert(a.begin() , 1);\n        a.push_back(1);\n         int n = a.size();\n        memset(dp , -1 , sizeof(dp));\n        return solve(a,0,n-1);\n    }\n};
[]