Friday, April 6, 2018

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.

No comments:

Post a Comment