[C++] Brute Force + Memoised + Bottom up
Brute force:-\n\nclass Solution {\npublic:\n    \n    int cut(vector<int> &b, int left, int right){\n        if(left+1==right) return 0;\n        int ans=0;\n  
Brute force:-\n```\nclass Solution {\npublic:\n    \n    int cut(vector<int> &b, int left, int right){\n        if(left+1==right) return 0;\n        int ans=0;\n        for(int i=left+1;i<right;i++){\n            int t1=cut(b,left,i);\n            int t2=cut(b,i,right);\n            int tans=b[left]*b[i]*b[right];\n            ans=max(ans,tans+t1+t2);\n        }\n        return ans;\n    }\n    \n    int maxCoins(vector<int>& a){\n        int n=a.size();\n        if(n==0) return 0;\n        if(n==1) return a[0];\n        vector<int> b(n+2);\n        b[0]=b[n+1]=1;\n        for(int i=1;i<=n;i++) b[i]=a[i-1];\n        return cut(b,0,n+1);\n    }\n};\n```\n\nMemoized:-\n```\nclass Solution {\npublic:\n    int dp[502][502];\n    int cut(vector<int> &b, int left, int right){\n        if(left+1==right) return 0;\n        if(dp[left][right]!=-1) return dp[left][right];\n        int ans=0;\n        for(int i=left+1;i<right;i++){\n            int t1=cut(b,left,i);\n            int t2=cut(b,i,right);\n            int tans=b[left]*b[i]*b[right];\n            ans=max(ans,tans+t1+t2);\n        }\n        return dp[left][right]=ans;\n    }\n    \n    int maxCoins(vector<int>& a){\n        int n=a.size();\n        if(n==0) return 0;\n        if(n==1) return a[0];\n        memset(dp,-1,sizeof(dp));\n        vector<int> b(n+2);\n        b[0]=b[n+1]=1;\n        for(int i=1;i<=n;i++) b[i]=a[i-1];\n        return cut(b,0,n+1);\n    }\n};\n```\nBottom up:-\n```\nclass Solution {\npublic:\n    int maxCoins(vector<int>& a){\n        int n=a.size();\n        if(n==0) return 0;\n        if(n==1) return a[0];\n        //memset(dp,-1,sizeof(dp));\n        vector<int> b(n+2);\n        b[0]=b[n+1]=1;\n        for(int i=1;i<=n;i++) b[i]=a[i-1];\n        int dp[b.size()][b.size()];\n        memset(dp,0,sizeof(dp));\n        for(int gap=2;gap<b.size();gap++){\n            for(int le=0;le<=b.size()-gap-1;le++){\n                int ri=le+gap;\n                for(int i=le+1;i<ri;i++){\n                    dp[le][ri]=max(dp[le][ri],dp[le][i]+dp[i][ri]+(b[le]*b[i]*b[ri]));\n                }\n            }\n        }\n        return dp[0][b.size()-1];\n    }\n};\n```
[]