Matrix Chain Multiplication | Memoization | C++
This question is similar to matrix chain multiplication.\nIf you think of bursting a balloon as multiplying two adjacent matrices, then this problem is exactly 
This question is similar to matrix chain multiplication.\nIf you think of bursting a balloon as multiplying two adjacent matrices, then this problem is exactly the classical DP problem Matrix-chain multiplication found in section 15.2 in the book Introduction to Algorithms (2nd edition).\n\nFor example, given [3,5,8] and bursting 5, the number of coins you get is the number of scalar multiplications you need to do to multiply two matrices A[3*5] and B[5*8]. So in this example, the original problem is actually the same as given a matrix chain A[1*3]*B[3*5]*C[5*8]*D[8*1], fully parenthesize it so that the total number of scalar multiplications is maximized, although the orignal matrix-chain multiplication problem in the book asks to minimize it. Then you can see it clearly as a classical DP problem.\n\nThanks to [GREEsDY](https://leetcode.com/GREEsDYhttp://) for the above explanation\n```\nint dp[502][502];\n    int solve(vector<int>& nums, int i, int j){\n        if(i>=j) return 0;\n        if(dp[i][j] != -1) return dp[i][j];\n        int ans = INT_MIN;\n        for(int k = i; k<=j-1; k++){\n            int temp = solve(nums,i,k) + solve(nums,k+1,j) + nums[k]*nums[i-1]*nums[j];\n            ans = max(ans,temp);\n        }\n        return dp[i][j] = ans;\n    }\n    int maxCoins(vector<int>& nums) {\n        nums.insert(nums.begin(),1);\n        nums.insert(nums.end(),1);\n        memset(dp,-1,sizeof dp);\n        return solve(nums,1,nums.size()-1); \n    }\n```
['Memoization']