C++ recursion with memorization
\nclass Solution {\npublic:\n    int dp[500][500] = {0};\n    int func(int start, int end, vector<int>& nums){\n        if(start > end)return 0;\n        if(dp[
```\nclass Solution {\npublic:\n    int dp[500][500] = {0};\n    int func(int start, int end, vector<int>& nums){\n        if(start > end)return 0;\n        if(dp[start][end] != 0)return dp[start][end];\n        int ret = 0;\n        int left = 1, right = 1;\n        if(start - 1 >= 0)left = nums[start-1];\n        if(end + 1 < nums.size()) right = nums[end + 1];\n        for(int i=start; i<=end; i++){\n            ret = max(ret, nums[i] * left * right + func(start, i-1, nums) + func(i+1, end, nums));\n        }\n        dp[start][end] = ret;\n        return ret;\n    }\n    int maxCoins(vector<int>& nums) {\n        if(nums.size() == 0)return 0;\n        return func(0,nums.size()-1, nums);\n    }\n};\n```
[]