How to Solve the Burst Balloons Problem like a Piece of Cake
The Burst Balloons Problem
Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
I encountered the Burst Balloons Problem on leetcode and this problem was surprisingly hard to solve(at least for me), because the test case is hard, the time limit is very strict and the best solution is surprisingly hard to comprehend. But don’t worry! We are going to move toward the best solution step by step and after you read this post, you are going to solve the Burst Balloons Problem like a piece of cake.
My first submission to the problem, a super straightforward recursive solution only passed 13/70 test cases before Time Limit Exceeded.
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def index(nums, i):
n = len(nums)
if i >=0 and i < n:
return nums[i]
return 1
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
if n == 2:
return nums[0]*nums[1]+max(nums[0], nums[1])
return max([index(nums, i-1)*index(nums, i)*index(nums, i+1)+self.maxCoins(nums[:i]+nums[i+1:]) for i in range(n)])This is a very simple top-down recursive approach which said “if there are n balloons, I can try to first burst one balloon and solve the remaining Burst Balloons problem with n-1 balloons.” It worked, but it’s also super slow.
As I analyzed this solution, I noticed that there were a lot of repeated sub-problems(Figure 1). Therefore, it is very natural to record the answers to these sub-problems so that when they are encountered the second time, you don’t need to solve them from scratch again and you can just look up their answers. This “recording answers to repeated sub-problems” method is called dynamic programming (such a mysterious sounding name).
A simple top-down recursive approach with memoization (which means recording) can be implemented with a dictionary like this. It is just almost the same as the previous recursive approach, but before it starts to solve a problem it first checks whether the answer to this problem already exists in the dictionary. In the dictionary, the keys are the sub-problem arrays and the values are the answers (maximum coins). If the answer doesn’t exist, it solves the sub-problem and records the answer.
class Solution(object):
def __init__(self):
self.d = {}
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if tuple(nums) in self.d:
return self.d[tuple(nums)]
def index(nums, i):
n = len(nums)
if i >=0 and i < n:
return nums[i]
return 1
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
if n == 2:
max_coins = nums[0]*nums[1]+max(nums[0], nums[1])
self.d[tuple(nums)] = max_coins
return max_coins
max_coins = max([index(nums, i-1)*index(nums, i)*index(nums, i+1)+self.maxCoins(nums[:i]+nums[i+1:]) for i in range(n)])
self.d[tuple(nums)] = max_coins
return max_coinsThis approach is still very straightforward and it is much faster than the previous simple recursive approach without memoization. It passed 31/70 test cases which was a huge improvement to the first approach (which only passed 13/70 test cases). However, this approach was still not fast enough and it couldn’t pass all the test cases because of Time Limit Exceeded. Even after I did some small refinements to the codes above (like rewriting the codes in a more efficient way and getting rid of all the balloons of zeros in advance), it only passed 33/70 test cases. Therefore, it’s obvious that a big algorithmic change is needed to pass all the test cases.
I noticed that with my simple recursive approach, I decreased the problem size by 1 in each step(Figure 1). For example, a problem with n=4 was turned into four problems each with n=3. Turning n to n-1 is a very small decrease in size because n-1 is still a pretty big number. Therefore, I should try to decrease the size of the problem even more in one step. It’s very natural to go for a decrease by half if a decrease by 1 is not enough. How do you cut the original balloons array by half?
A very important fact is that if a balloon in the middle is not bursted until the end, the balloons array to its left and the array to its right are independent. The left part and the right part are independent if they are always separated by a balloon.
If we assume a certain balloon is the last one to be bursted, we can treat the array to its left and the array to its right as two independent Burst Balloons problems, thus reducing the problem size significantly. The top-down divide and conquer recursive approach is as belows:
max_coins = 0
for every balloons[i] in balloons:
burst its left part
burst its right part
burst balloons[i] after all other balloons are bursted
coins = add up all the coins gained in this process
if max_coins < coins:
max_coins = coins
return max_coinsAdding a dictionary to record answers to sub-problems, the complete program is as belows:
class Solution(object):
def __init__(self):
self.d = {}
def recursive_maxCoins(self, nums, lower, upper):
if tuple(nums[lower-1:upper+2]) in self.d:
return self.d[tuple(nums[lower-1 : upper+2])]
max_coins = 0
for i in range(lower, upper+1):
coins = nums[lower-1] * nums[i] * nums[upper+1]
coins += self.recursive_maxCoins(nums, lower, i-1)
coins += self.recursive_maxCoins(nums, i+1, upper)
if coins > max_coins:
max_coins = coins
self.d[tuple(nums[lower-1:upper+2])] = max_coins
return max_coins
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + [num for num in nums if num != 0] + [1]
n = len(nums) - 2
return self.recursive_maxCoins(nums, 1, n)This approach increased the speed significantly and it passed 69/70 test cases! A huge progress! Right now, we are using a clever way to reduce the problem size and a clever way to store answers to sup-problems, but these are still not enough. The program is still not fast enough to pass the hardest test case. What more can be done?
Since this program is using a top-down approach, inducing a lot of overheads, a promising direction to make this program faster is to write its equivalent bottom-up approach. In the spirit of dynamic programming, we want to solve all the smaller sub-problems first before trying to solve bigger problems, because solving bigger problems needs the answers to smaller problems. For example, we want to know how to optimally burst all 2-balloon arrays and 3-balloon arrays before trying to solve a 4-balloon array. A 4-balloon array can be divided into smaller array as belows (Figure 2):
The complete codes are as belows:
This program first gets rid of all the zeros, adds a 1 at the beginning and adds a 1 at the end. The 2-D list dp is for storing answers to sub-problems. dp[left][right] is the maximum coins gained when bursting all the balloons between (not include) left and right. Therefore, the dp[0][n-1] is the ultimate answer.
In this program, we first solved all the sub-problems of length 1, and then length 2, and then length 3….at last length n-2 which is the length of the balloon array not counting the head and tail. I will illustrate this program with a simple example [3, 1, 5, 8] and a picture below(Figure 3). Bigger problems are solved by using answers to smaller problems as illustrated by Figure 2.
Finally, this program passed all the test cases in 324ms! Hurray! Although I went through a whole evolution to get to the final program, it is actually very short! Once you comprehend the thinking behind this program, you can solve this hard problem like a piece of cake!
