# Python solution with detailed explanation

• 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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.