For those who are not able to understand any solution [WITH DIAGRAM]
I saw multiple solutions on the discussions forum and was not able to figure out what they were trying to explain. So, I came up with solution myself and will t
I saw multiple solutions on the discussions forum and was not able to figure out what they were trying to explain. So, I came up with solution myself and will try to explain it in the simplest way. If you are clear with the subproblems and are just confused with the implementation, you can jump directly to the diagram below.\n<BR>\n\n**Bruteforce:** Generate all permutations for the ordering of balloons and check which permutation yields the best profit. But it will take O(n!) time.\n<br>\n\n**DP Solution:** For a DP solution to exist, we need to define the subproblems. Let\'s define the problem first as:\n\n\tsolve(nums, i, j)\n\nby which I mean that we need to burst balloons starting from index i to index j. At the beginning, they\'ll be 0, nums.size()  -1 respectively. Let\'s suppose we burst the kth balloon in the first chance. We will get **nums[k-1] * nums[k] * nums[k+1]** coins. Now let\'s define the subproblems as:\n```\nsolve(nums, i, k - 1) , solve(nums, k + 1, j)\n```\nAs the balloon k is already burst, we solve the subproblems from i to k -1 and k + 1 to j. But wait, what\'s going wrong here? The subproblem **solve(nums, i, k - 1)** and **solve(nums, k + 1, j)** are not independent since after bursting **kth balloon**, balloon k - 1 and k + 1 have become adjacent and they will need each other in order to calculate the profit.\n\nSo, as we saw that if we choose the kth balloon to be the first one to be burst, we can\'t make the subproblems independent. Let\'s try the other way round. We choose the kth balloon as the **last one to be burst**. Now the subproblems will become independent since **(k - 1)th balloon** and **(k + 1)th balloon** won\'t need each other in order to calculate the answer.  (Try it out using pen and paper). \n\nNow for each **k** starting from i to j, we choose the kth balloon to be the last one to be burst and calculate the profit by solving the subproblems recursively. Whichever choice of k gives us the best answer, we store it and return. \nImportant point to be noted here is that the balloons in the range **(i, k - 1) and (k + 1, j)** will be burst **BEFORE** kth balloon. So, when we burst the kth balloon, the profit will be ***nums[i - 1] * nums[k] * nums[j + 1]*** PROVIDED that index i - 1 and j + 1 are valid. \n<br>\n\n**STILL CONFUSED?**\n---\nDon\'t worry, the example given in the diagram below will make things SUPER CLEAR! 2 dummy balloons each with value 1 are inserted to handle the corner balloons in the original array. \n***[Choices of **k** in the below diagram are random and don\'t necessarily yield the optimal solution.]***\n\n![image](https://assets.leetcode.com/users/images/1bafbe44-cb85-4ade-adb5-54ee5095baea_1602579692.7557607.png)\n\n<br>\n\nCODE\n---\n\n```\nclass Solution {\npublic:\n    int n;\n    int t[501][501]; // For memoization\n    int solve(vector<int> &nums, int i, int j){\n\t\t// BASE CASES\n\t\tif(i > j)\n\t\t\treturn 0;\n        if(i == j){    // Only one element exists\n            int temp = nums[i];\n            if(i - 1 >= 0)  \n                temp *= nums[i - 1];\n            if(i + 1 < n)\n                temp *= nums[i + 1];\n            return temp;\n        }\n\t\tif(t[i][j] != -1)  // Check if the solution is already stored for this subproblem\n\t\t\treturn t[i][j];\n        int ans = 0;\n\t\t\n\t\t// For all elements in the range i to j, we choose all of them one by one \n\t\t// to make them the last balloon to be burst. \n        for(int k = i; k <= j; k++){\n\t\t\n\t\t    // Burst the kth balloon after bursting (i, k - 1) and (k + 1, j) balloons\n            int temp = nums[k];\n\t\t\t\n            if(j + 1 < n)  // As balloon j + 1 will become adjacent to k after bursting  k + 1 to j balloons\n                temp *= nums[j + 1];\n\t\t\t\t\n            if(i - 1 >= 0) // As balloon i- 1 will become adjacent to k after bursting  i  to k -1 balloons\n                temp *= nums[i - 1];\n\t\t\t\t\n\t\t\t// Recursively solve the left and right subproblems and add their contribution\n            temp += (solve(nums, i, k - 1) + solve(nums, k + 1, j));\n\t\t\t\n\t\t\t// If this choice of k yields a better answer\n            ans = max(ans, temp);\n        }\n        return t[i][j] = ans;\n    }\n    \n    int maxCoins(vector<int>& nums) {\n        memset(t, -1, sizeof(t));\n\t\t\n        // Insert two dummy balloons of value 1 to handle the balloons on the corner.\n\t\tvector<int> arr = {1};\n        for(int x: nums) \n\t\t\tarr.push_back(x);\n        arr.push_back(1);\n        n = arr.size();\n\t\t\n\t\t//Start from i = 1 and j = arr.size() - 2 since first and last balloons are dummy.\n        return solve(arr, 1, arr.size() - 2);\n    }\n};\n```\nPlease don\'t go without upvoting if it helped you!
['Dynamic Programming', 'Memoization', 'C']