Leetcode 312: burst ballons

March 26, 2017

Introduction 

Problem statement

Julia has some difficulty to figure out dynamic programming from the very beginning for unseen problems, so she likes to vote up virtually the analysis of burst ballons on this blog.

The most important message is like the conversation, let us read the sentence by sentence together here.

"This is the kind of problem we use dynamic programming. WHY? it's very challenging to figure out what's the pattern of optimal burst order. In fact, there's no clear rule that makes sense. Shall we burst the balloon with maximum coins? Or shall we burst the one with least. This is the time we introduce Dynamic Programming, as we want to solve the big problem from small subproblem. It is clear that the amount of coins you gain relies on your previous steps. This is a clear signal of using DP.

The hard part is to define the subproblem. Think out what is clear in this problem? Let's scale this problem down. What is the fact you know for sure? Say if the array has only 1 balloon. The maximum coin would be the coin inside this ballon. This is the starting point! So let's move on to array with 2 balloons. Here, we have 2 cases, which of the balloon is the last one. The last one times the coins in boundary is the gain we get in the end. That is to say, last balloon is the key. Since we don't know the pattern of optimal. We just blindly iterate each balloon and check what's total gain if it's the last ballon."

But after those two paragraphs, Julia got lost the formula:

Let's use dp[i][j] to denote maximum gain from balloon range i to j. We try out each balloon as last burst in this range. Then the subproblem relation would be:

foreach k in i to j:
 dp[j][i] = max(array[j-1]*array[k]*array[i+1] + dp[j][k-1] + dp[k+1][i], dp[j][i]);

Algorithm study

Study the blog about burst ballons first. (March 26, 2017, 11:01am - 11:15am)
Watch the video - burst ballons.  (March 26, 2017, 11:15am - 11:30am, 2:40pm - 3:00pm)
Continue to read Leetcode discussion (March 26, 2017, 12:00pm - 12:30pm)

Thinking process

Continue to read Leetcode discussion (March 26, 2017, 12:00pm - 12:30pm)

Julia is getting smarter, she starts to read more discussions from Leetcode discussion instead of blogs written in Chinese, she values the discussion with vote systems.

Discussion with over 400 up-votes - link is here.

Divide and conquer   vs  reverse thinking

Continue to write C# code using sample code (March 26, 2017, 12:30pm - 12:58pm)

Julia's C# practice, pass all Leetcode test cases. Code link is here.

It is not easy to figure out the dynamic programming solution the first time, what I can do is to read the leetcode discussion again, and follow the thought process, from recursive function, naive solution first, and then try to move to next stage.

Notes from discussions:
1. Coursera - algorithm 2 - optimal binary tree DP problem
2. GeekforGeeks algorithm - optimal binary tree DP problem

Thought process rehearsal 

Julia likes to follow up the thought process closely. That is most important part to learn, how to approach the problem naively first, and then move forward with the hints, and problem solving skills.

The most naive idea the backtracking

We have n balloons to burst, which mean we have n steps in the game. In the ith step we have n - i balloons to burst, i = 0 ~ n - 1. Therefore we are looking at an algorithm of O(n!). Well, it is slow, probably works for n < 12 only.

Well, we can find that for any balloons left the maxCoins does not depends on the balloons already bursted. This indicate that we can use memorization (top down) or dynamic programming (bottom up) for all the cases from small numbers of balloon until n balloons. How many cases are there? For k balloons there are C(n, k) cases and for each case it need to scan the k balloons to compare. The sum is quite big still. It is better than O(n!) but worse than O(2ⁿ).

Better idea using recursive and memorization or DP

We then think can we apply the divide and conquer technique? After all there seems to be many self similar sub problems from the previous analysis.

Well, the nature way to divide the problem is burst one balloon and separate the balloons into 2 sub sections one on the left and one one the right. However, in this problem the left and right become adjacent and have effects on the maxCoins in the future.

Then another interesting idea come up. Which is quite often seen in dynamic programming (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 instead of divide the problem by the first balloon to burst, we divide the problem by the last balloon to burst.

Why is that? Because only the first and last balloons we are sure of their adjacent balloons before hand!

For the first we have nums[i-1]*nums[i]*nums[i+1] for the last we have nums[-1]*nums[i]*nums[n].

OK. Think about n balloons if i is the last one to burst, what now?

We can see that the balloons is again separated into 2 sections. But this time since the balloon i is the last balloon of all to burst, the left and right section now has well defined boundary and do not affect each other! Therefore we can do either recursive method with memoization or dp.

Final

Here comes the final solutions. Note that we put 2 balloons with 1 as boundaries and also burst all the zero balloons in the first round since they won't give any coins.

The algorithm runs in O(n³) which can be easily seen from the 3 loops in dp solution.

Video Study

Watch the video - burst balloons.  (March 26, 2017, 11:15am - 11:30am, 2:40pm - 3:00pm)

19:08/ 27:01

Burst balloons to maximum value, Julia copied and paste from the video: