1 #define maxn 1000000 2 #define _for(i,a,b) for(int i = (a);i < (b);i ++) 3 #define pb push_back 4 class Solution 5 { 6 public: 7 int dp[503][503]; 8 int ms(vector<int>& nums,int le,int ri) 9 { 10 11 if(le==ri-1) 12 return 0; 13 if(dp[le][ri]!=-1) 14 return dp[le][ri]; 15 16 int rnt = INT_MIN; 17 for(int i = le+1;i < ri;i ++) 18 rnt = max(rnt,ms(nums,le,i)+ms(nums,i,ri) 19 +nums[le]*nums[i]*nums[ri]); 20 return dp[le][ri] = rnt; 21 } 22 int maxCoins(vector<int>& nums) 23 { 24 memset(dp,-1,sizeof(dp)); 25 vector<int> arr(nums.size()+2); 26 _for(i,0,nums.size()) 27 arr[i+1] = nums[i]; 28 arr[0] = arr[nums.size()+1] = 1; 29 return ms(arr,0,nums.size()+1); 30 } 31 };