Julia has some difficulty to figure out dynamic programming from the very beginning for unseen problems, so she likes to vote up 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:
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]);
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)