Leetcode 312: Burst balloons

April 6, 2018

Introduction

It is a hard level algorithm, so I like to work on the algorithm over ten times. I like to spend time to read this blog written in Chinese, and then try to understand better about the algorithm.

Here is the gist I created for blog study.

My favorite algorithm

It is the first time I read this analysis in Chinese. I could not believe that the analysis is such a good one.

I have to learn how to break into two subproblems and also two of them are independent.

Algorithm study: 95 algorithm videos (II)

April 20, 2018

Introduction

It is hard level algorithm called Leetcode 312: Burst Balloons. And the video is 20 minutes, I spent the time to watch the video, staying at home for one day vacation. I enjoyed the learning of the algorithm.

It is interesting for me to learn the dynamic programming through the video. I like to evaluate the author and see how good he is. I know that he is working for Facebook.

Leetcode 312: Burst Balloons

I like to talk about a screenshot and discuss the layout of dynamic programming algorithm presented by basksetwangcoding.

First step, I need to define state for the dynamic programming algorithm.

Next step, I need to define initialization step.

Third step, I need to define the function, problem and subproblem how to connect each other.

[left][right] = Max(i: [left + 1, right - 1])

For each subproblem, coin[i] * coin[left] * coin[right] + [left][i] + [i][right - 1]

Fourth step, I need to define result: [0][n - 1]

I need to put together a simple example to explain the solution to the peer. Here it is the example:

  1    2    3    4   5   6   7  8  9

Algorithm practice

Here is my C# practice.

Algorithm study: 95 algorithm videos (I)

April 6, 2018

Introduction

It is a hard level algorithm called Leetcode 312: Burst Balloons in Leetcode.com. I like to study the algorithm again by watching the teaching video here.

I could not believe that I finally have time to write code for the algorithm on April 25, 2018.

Leetcode 312: Burst Balloons Algorithm practice

I started to work on the algorithm on April 24, 2018. I have to learn the algorithm by working on a simple test case [3, 1, 5, 8] with the maximum value 167 based on Leetcode 312 problem statement. What I did is to write C# code based on the idea based on the video provided by a facebook engineer.

I calmed down and thought about how to write this dynamic programming solution, I told myself that I should take the time to think and do not rush, read other people's source code.

Basic ideas are simple. Define the base cases first, and then bottom up build the dynamic programming table.

I spent more than 40 minutes to write down the code on the paper. I put the code in Visual studio and debug the code. Apply the test case [3, 1, 5, 8]. But the code does not work, the value is much bigger than 167. Actually it is 218.

Here is my C# practice with some bugs. I need to figure out my problem in the algorithm. 

I could not believe that I could not count the correct number. The number is too big. In theory, it should be the error from the base case, the logic of recurrence is simple and I copied from the facebook engineer presented in the above video. But I need to train myself on this bug finding process. 

Find the bug

It is time for me to read discussion panel of Leetcode 312, I read a few of them, but the dynamic programming idea is different. So I continued to google and read a few blogs. One of blogs is very good since the blogger works for Microsoft.

But I still could not apply my case. The dynamic programming method in those blogs are inclusive, not exclusive.

Questioning the base case

Finally I started to question my base case, what is the value dp[i, i+1], in other words, keep ith and (i + 1)th balloon, then there is no balloon to burst. My answer is numbers[i] * numbers[i + 1], that is too much. So I changed to one. I ran the code still not the correct. So I finally know that it should be 0.

Although it takes me a lot of hours to learn the algorithm, but I think that I do right thing for myself.

Here is my C# code to pass Leetcode 312 online judge.

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: