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.