Leetcode 312: Burst Balloons

February 17, 2016 

Spent 10 minutes to work on an example, int[] A = {1,2,3,4,5}, and see how to work out maximum coins? 

Need to figure out Dynamic Programming formula, how to get the analysis done in a reasonable way? The problem is rated as medium, hard. So, take time to figure out. Since most of questions are easy to medium, let Julia put some creative, passion and other important things into the analysis, get more confident on hard questions.  

Feb. 18, 2016 continue to work on the analysis
One phrase Julia likes is "Things have to do is called stress, but thing love to do is called passion". Make this analysis is Julia's first passion practice - how to approach the problem? 

Try to work on brute force solution first. 
work on example, int[] A = {1, 2, 3, 4, 5}
First one to burst, 5 choices:any one of them, so 
case 1: burst 1, left: {2, 3, 4, 5}
        2: burst 2, left: {1, 3, 4, 5}
        3: burst 3, left: {1, 2, 4, 5}
        4: burst 4, left: {1, 2, 3, 5}
        5: burst 5, left: {1, 2, 3, 4}

And choose max value from the above 5 case. Each case is a subproblem, find max value from array size of 4. <- not exactly <- ? Julia, miss something important here 

Use start, end index of array, and max value is denoted as P(start, end)
so, P(0, 4) can be divided into 5 cases:
case 1: burst 1, left: P(1,4), how to calculate the value, A[0], A[1], P(1,4), value = A[0]*A[1] + P(1,4)
case 2: burst 2, left: P(0,0), P(2, 4), value = P(0,0) + A[0]*A[1]*A[2] + P(2,4)
...
case 5: burst 5, left: P(0,3), value = P(0,3) + A[3]*A[4], 

So, the max value is P(0,4), the value is max value of subproblems. Formula: 

 max{P(0,k-1) + product(k) + P(k+1,n)}, k = 0,1,.., n

Now, the dynamic programming formula is constructed. 

So, write the design of DP - memorization, P(start, end) - declare two dimension array vector[n][n] 

Feb. 19, 2016 
Still need to work on implementation, go for DP - how to build loops?
Go for recursive solution - 
Go for Divide and Conquer solution - 

Here is the blog she starts to read.

  http://bookshadow.com/leetcode/

  https://www.hrwhisper.me/leetcode-algorithm-solution/

  http://www.cnblogs.com/grandyang/p/4606334.html

  http://www.cnblogs.com/EdwardLiu/tag/Leetcode/

  http://www.jiuzhang.com/problem/

Similar problem like Floyd shortest distance.