C++ DP solution with very detailed explanation starting from DFS
So, the solution I have started with was DFS solution where at every level of recursion you pick an unused baloon, find its left and right neighbors\nThen, you 
So, the solution I have started with was DFS solution where at every level of recursion you pick an unused baloon, find its left and right neighbors\nThen, you compute how much coins you are going to earn by doing that and make a recursive call to compute the rest.\nAgain, you do it for EVERY balloon on this recursive level. \nThis way we are trying all permutations of the baloons of size n.\nWhat is the complexity of this? \nAt the top level, your branch factor is n because there are n baloons to burst. Then, on the next level for each of those n branches, the branching factor is n-1 and so on and so forth until branch factor becomes 0 when you have burst all the balloons. The depth of this tree is n.\nThe number of leafs will be n*(n-1)*(n-2)...1 which is n!. Now, every time you branch out, you do O(n) to find left and right baloons that haven\'t been used yet(assuming you are marking baloons with -1 rather than passing the memory). For each node in this tree, you are doing O(n). So, for each leaf, you are doing n*n work because n is the depth and n is the work at each level. So, it seems like it is n^2 * n!.\nHorrible!\nIf you try to use this recurrence relation for DP, you will end up with a much better solution but still not perfect.\n\nNow, the key here is to use another recurrence relation. Instead of choosing the first baloon to burst and then going from there, use the last baloon to burst and use that. \nWhy is that? \nWell, because it is very easy to compute coins for the last baloon. That\'s one part but not the most important one.\nBy bursting left subarray and right subarrays before you burst yourself, you are not letting them intermix the orderings. To intermix, they need to break the wall between them which is you. And you burst yourself last. So, all you need to know is the best score for the left subarray, then right subarrray and then add yourself. The order left, rigth or right, left doesn\'t matter.\nI will also quote from top solution:\n```\nThen another interesting idea come up. Which is quite often seen in dp problem analysis. That is reverse thinking. Like I said the coins you get for a balloon does not depend on the balloons already burst. Therefore\ninstead of divide the problem by the first balloon to burst, we divide the problem by the last balloon to burst.\n```\nMoving on to the logic.\nLet\'s say you had \n[3, 1, 5, 8]\nIf you choose 5 as your last baloon, then score is 1 * 5 * 1, where ones are virtual bounds as the rest are burst because this is your last baloon.\nAgain, you do this for every baloon and ask left left subarray to compute best possible coin sum by bursting all of them and right subarray to compute best possible coin sum by bursting all of them.\nOn the topmost level, you are going to try out all permutations ending with 0,1,2,3..n-1 baloon.\nThis works because let\'s say when you are trying out to burst baloon at index 4, you make recursive call to the part [0,3] and [5, end]. They will also try out all possible ordering of baloons in their subarray and return the result to you. \nSo, this way we are also considering all the options except that now, at every level we are spending constant time instead of O(n).\nThis is great!\nHere is where comes DP.\nHow, do you compute best for subarray of size 1? You ask what is the best left subarray score and it is zero because it is empty. Same with the right one. Now, you have to compute coins you are bringing to the table. Again, [1, coins, 1] which is 1 * coins * 1. Cool.\nYou have solved the problem for all sizes of 1. Do the same for size 2.\nExample with size 3:\nNow, imagine we have array of size 3 [3, 1, 5] and you have computed the results for all subarrays of sizes 1 and 2.\nYou go through each element in it and try that element as last one to burst.\nFor example, let\'s burst 3 as last. Then, left gives us nothing because there is nothing to the left. 3 brings total of 1(left virtual boundary)*3(coins)*8 (because this is the first value outside of our burst range to the right). Then, we ask how much right subarray [1, 5] is going to bring us. Doing this, you will get bottom up DP solution. It is O(n^3) time and O(n^2) space. where dp[i][j] represents max amount of coins to burst baloons in range [i, j].\n```\n    int maxCoins(vector<int>& nums) {\n        int orig_size = nums.size();\n\t\t// virtual bounds for simplicity\n        nums.insert(nums.begin(), 1);\n        nums.insert(nums.end(), 1);\n        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));\n        int len = 1;\n\t\t// compute all possible sizes as subarray of size len needs to know results for len-1, len-2 and etc.\n        while(len <= orig_size){\n\t\t    // start is i\n            int i = 1;\n\t\t\t// end included\n            int end = i + len - 1;\n\t\t\t// this window has size len, then slide it to the left by for as long as you can.\n            for(; end < (nums.size() - 1); i++, end++){\n\t\t\t    // in each range, try every element as last baloon to burst, compute what it brings \n\t\t\t\t// and you computed results for left and right parts\n                for(int last = i; last <= end; last++){\n                    int left_range_res = dp[i][last - 1];\n                    int right_range_res = dp[last + 1][end];\n                    int coins_in_last = nums[last];\n\t\t\t\t\t// nums[i - 1] is the first baloon to the left that isn\'t burst so it is your left boundary(it might be virtual)\n\t\t\t\t\t// nums[end + 1] is the first baloon to the right that isn\'t burst so it is your right boundary(it might be virtual)\n                    int last_burst_score = nums[i - 1] * coins_in_last * nums[end + 1];\n                    dp[i][end] = max(dp[i][end], left_range_res + last_burst_score + right_range_res);\n                }\n            }\n\t\t\t// now find results for len+1 using what we have computed.\n            len++;\n        }\n\t\t// this is because we have added two virtual bounds.\n        return dp[1][orig_size];\n    }\n```
[]