**Solution**

**Burst Balloons** https://leetcode.com/problems/burst-balloons/

**Brute Force Backtracking Solution**

- 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.

```
class Solution(object):
def get_key(self, nums):
return "_".join(map(str, nums))
def helper(self, nums, cache):
if nums == []:
return 0
else:
k = self.get_key(nums)
if k in cache:
return cache[k]
cache[k] = float('-inf')
for i, x in enumerate(nums):
left, right = nums[i-1] if i > 0 else 1, nums[i+1] if i+1<len(nums) else 1
cache[k] = max(cache[k], self.helper(nums[0:i] + nums[i+1:], cache) + left*right*x)
return cache[k]
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return self.helper(nums, {})
```

**Optimized Solution using Divide and Conquer**

- 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.
- Instead, the insight is to define a sub-problem as finding the maximum coins possible within [low, high] of nums array.
- Now let us pick an index i as the last burst balloon within that range.
- 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]
- 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.
- 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:

dp[low,high] = max(dp[low,high], nums[i] * nums[low-1] * nums[high + 1] + dp[low, i-1] + dp[i+1, high]) - Simply use caching to solve this recurrence.
- 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.

```
from collections import defaultdict
class Solution(object):
def helper(self, nums, low, high, cache):
if low > high:
return 0
elif low in cache and high in cache[low]:
return cache[low][high]
else:
for i in range(low, high+1):
left_half, right_half = self.helper(nums, low, i-1, cache), self.helper(nums, i+1, high, cache)
left, right = nums[low-1] if low > 0 else 1, nums[high+1] if high+1<len(nums) else 1
cache[low][high] = max(cache[low][high], left_half + right_half + left*nums[i]*right)
return cache[low][high]
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
cache = defaultdict(lambda: defaultdict(int))
return self.helper(nums, 0, len(nums)-1, cache)
```