MCM+memorisation (simple and elegent solution) commented code
```\nclass Solution {\npublic:\n  \n  //MCM +memo taking every kth balloon bursting in the last;\n  \n  \n  int memo[501][501];\n  int solve(vector &nums,int i 
```\nclass Solution {\npublic:\n  \n  //MCM +memo taking every kth balloon bursting in the last;\n  \n  \n  int memo[501][501];\n  int solve(vector<int> &nums,int i ,int j){\n    if(i>j)return 0;\n    if(memo[i][j]!=-1)return memo[i][j];\n    \n    int max_score=INT_MIN;\n    for(int k=i;k<=j;k++){\n      int curr_score=nums[i-1]*nums[k]*nums[j+1];\n      int temp_score=curr_score+solve(nums,i,k-1)+solve(nums,k+1,j);\n      if(temp_score>max_score)max_score=temp_score;\n    }\n    return memo[i][j]=max_score;\n  }\n    int maxCoins(vector<int>& nums) {\n      memset(memo,-1,sizeof(memo));\n      //-1 th position pe && nth pos pe 1 score milega (by example)\n      nums.insert(nums.begin(),1);\n      nums.push_back(1);\n      \n      return solve(nums,1,nums.size()-2);\n    }\n};
['Dynamic Programming', 'C', 'C++']