[C++] Based On Matrix Chain Multiplication
\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(),1);\n        nums.push_back(1)
```\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(),1);\n        nums.push_back(1);\n        int n = nums.size();\n        dp.resize(n, vector<int>(n));\n        return helper(nums,1,n-1);\n    }\n    int helper(vector<int>& nums,int start,int end){\n        if(start >= end){\n            return 0;\n        }\n        if(dp[start][end] != 0){\n            return dp[start][end];\n        }\n        int res = INT_MIN;\n        for(int k = start; k < end; k++){\n            int temp = helper(nums,start,k) + helper(nums,k+1,end) + nums[start-1]*nums[k]*nums[end];\n            res = max(res,temp);\n        }\n        dp[start][end] = res;\n        return res;\n    }\n};\n```
[]