Detailed Explanation + Readable explained code
Intuition-\n\t1) Clearly the brute force solution would be to try all possible combinations of popping the balloons and so First we have n choices to select 1 t
Intuition-\n\t1) Clearly the brute force solution would be to try all possible combinations of popping the balloons and so First we have n choices to select 1 to burst and then in the next step n-1 choices ,,,,,,,,and in the end we are left with the only balloon ..So clearly it\'s a n! solution which will work for n<=10\n\t2) So clearly we have to find a way to break this problem into smaller parts.  A natural approach would be to separate the array on the basis of what if we pop a particular balloon first and then separate the array into 2 parts.  SO if i have 3,1,4,8,9 and i guess that a balloon 4 should be popped first ,would it make the 2 parts [3,1] &[8,9] results independent of each other.I mean can we forget while calculating [3,1] that [8,9] exists. Clearly Not, \nWhy?\nbecause even if we knew in [3,1] the correct order we have to pop these balloons we still dont know the exact right neighbor of these elements ,rigght neighbor could be 8 or 9 depending on which one is popped earlier.\nSo what if ,we could find a definition of dp that could help us make these 2 parts independent of each other.\n\n3) So instead of picking or guessing which balloon to pop first we guess which balloon is popped last. So it means if [1,2,3,4,5] if in this array we knew that element 3 was the last one to be popped and then we would know that subparts[1,2] would always have right border as 3 because it\'s the last one to be popped  and similarly the right part[4,5] would always know it\'s left border\n\nNow onto the solution->\nwe define **dp[left][right]to be maximum value we can get on bursting thee balloons in the subarray nums[left,right](inclusive) considering the fact that other balloons are still not burst ..**\nAnd so \nHere\'s the code\n```\nint f(vector<int>&nums,vector<vector<int>>&dp)\n    {\n        int n=nums.size();\n        for(int k=1;k<n-2;k++)\n        {\n            for(int j=1;j<n-k-1;j++)\n            {\n                for(int i=j+1;i<j+k;i++)\n                {\n                    dp[j][j+k]=max(dp[j][j+k],dp[j][i-1]+dp[i+1][j+k]+nums[j-1]*nums[j+k+1]*nums[i]);\n                }\n                dp[j][j+k]=max(dp[j][j+k],nums[j]*nums[j-1]*nums[j+k+1]+dp[j+1][j+k]);\n                dp[j][j+k]=max(dp[j][j+k],nums[j+k]*nums[j-1]*nums[j+k+1]+dp[j][j+k-1]);\n            }\n        }\n        return dp[1][n-2];\n    }\n    int maxCoins(vector<int>& nums) {\n        nums.push_back(1);\n        nums.insert(nums.begin(),1);\n        vector<vector<int>>dp(nums.size(),vector<int>(nums.size()));\n        for(int i=1;i<nums.size()-1;i++)\n            dp[i][i]=nums[i]*nums[i+1]*nums[i-1];\n        return f(nums,dp);\n    }\n```\nCode Explanation->we have added fake nodes or balloons with value 1 so that we dont have to check for out of bound error again and again.\nk is the length of the interval .\nwhy is it kept in outer bracket because once we pop a balloon the length of subparts will decrease by 1 atleast,\nso solutions of smaller interval are needed.\nnow j is the starting point of the interval and so naturally j+k is the endpoint \nnow we consider each balloon to be popped last and use the solution to the solved subproblem\nNow explaining the dp recurrence relation->\ndp[left][right]=max(dp[left][right],dp[left,i-1]+dp[i+1,right]+nums[i]*nums[left-1]*nums[right+1]);\nthe first term of max is a no brainer.However the second term implies that if we knew that ith was the last burst balloon .like for ex nums=[1,2,3,4,5]\nand we are calculating dp[1,3](0 based indexing) and we knew that 2nd index element is the last balloon so in the end nums =[1,3,5] so popping 3 (2nd index element ) would yield product of nums[left-1] which is nums[0]=1 , nums[right+1] which is nums[4]=5 and nums[2]=3\nso before breaking into subparts we take this factor nums[i]*nums[left-1]*nums[right+1] into consideration.\n\nUpvote if you like my explanation and if you are still confused ,feel free to ask any questions.
['Dynamic Programming', 'C']