Python solution with detailed explanation
Solution\n\nBurst Balloons https://leetcode.com/problems/burst-balloons/\n\nBrute Force Backtracking Solution\n The first naive solution is to use back-tracking
**Solution**\n\n**Burst Balloons** https://leetcode.com/problems/burst-balloons/\n\n**Brute Force Backtracking Solution**\n* The first naive solution is to use back-tracking. Then you can optimize back-tracking using caching. Back-tracking will have a complexity of O(N!). With cache optmization, some pruning will happen in the tree, but its complexity will still be a lot.\n\n```\nclass Solution(object):\n    def get_key(self, nums):\n        return "_".join(map(str, nums))\n    \n    def helper(self, nums, cache):\n        if nums == []:\n            return 0\n        else:\n            k = self.get_key(nums)\n            if k in cache:\n                return cache[k]\n            cache[k] = float('-inf')\n            for i, x in enumerate(nums):\n                left, right = nums[i-1] if i > 0 else 1, nums[i+1] if i+1<len(nums) else 1\n                cache[k] = max(cache[k], self.helper(nums[0:i] + nums[i+1:], cache) + left*right*x)\n            return cache[k]\n    \n    def maxCoins(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        return self.helper(nums, {})\n```\n\n**Optimized Solution using Divide and Conquer**\n* Try thinking using divide and conquer. Pick an index, burst that balloon. Issue is that post bursting, the left and right halves around the burst balloon share a common boundary.\n* Instead, the insight is to define a sub-problem as finding the maximum coins possible within [low, high] of nums array. \n* Now let us pick an index i as the last burst balloon within that range.\n* The last burst balloon will be padded with nums[low-1] and nums[high+1]. So its contribution will be nums[low-1] * nums[high+1] * nums[i]\n* nums[i] is the last balloon to be burst which yield maximum coins when considering only ballons within nums[low] to nums[high]. Now when we reach nums[i] ready to be burst, what balloons is it padded with? It will be padded with nums[low-1] and nums[high+1]. Thus you need you take their contribution. This part is tricky - give it a careful though. If you understand the sub-problem formulation, then it is easy.\n* Now we can define a recursive formulation. Given that we pick index i as the last burst balloon to burst, the maximum coins which can be collected using balloons from low to high is:\ndp[low,high] = max(dp[low,high], nums[i] * nums[low-1] * nums[high + 1] + dp[low, i-1] + dp[i+1, high])\n* Simply use caching to solve this recurrence.\n* What is the complexity? Answer is: O(N^3). Why? There O(N^2) sub-problems (evident from the matrix to cache solutions). Each problem is O(N) complexity.\n\n```\nfrom collections import defaultdict\nclass Solution(object):\n    def helper(self, nums, low, high, cache):\n        if low > high:\n            return 0\n        elif low in cache and high in cache[low]:\n            return cache[low][high]\n        else:\n            for i in range(low, high+1):\n                left_half, right_half = self.helper(nums, low, i-1, cache), self.helper(nums, i+1, high, cache)\n                left, right = nums[low-1] if low > 0 else 1, nums[high+1] if high+1<len(nums) else 1\n                cache[low][high] = max(cache[low][high], left_half + right_half + left*nums[i]*right)\n            return cache[low][high]\n    \n    def maxCoins(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        cache = defaultdict(lambda: defaultdict(int))\n        return self.helper(nums, 0, len(nums)-1, cache)\n```
[]