Bursting the Balloons
Balloons are in a row, each holding a number. Bursting a balloon scores the product of its own number and the numbers of its CURRENT left and right neighbours. A missing neighbour, because it has already burst or is past the end, counts as 1.
Bursting changes who is adjacent to whom. Print the largest total score.
3 1 5 8 -> 167
1 5 -> 10
## Why the obvious state does not work
The natural attempt is dp[i][j] meaning "the best score from bursting everything in
i..j", with the recurrence choosing which balloon to burst FIRST.
That fails. Once the first balloon is burst, the two halves are no longer independent: a balloon in the left half can end up adjacent to one in the right half, so their scores depend on each other.
An interval DP needs the split to make the halves independent, and choosing the first burst does not.
## Reverse the question: which balloon is burst LAST
Fix the range (i, j) as an OPEN interval, meaning balloons strictly between i and j,
with i and j themselves still intact.
Suppose balloon k inside that range is the LAST one burst. At that moment everything else
inside is gone, so its neighbours are exactly i and j, and it scores v[i] * v[k] * v[j].
Everything burst before it splits cleanly: those in (i, k) never interact with those in
(k, j), because k sits between them until the very end.
dp[i][j] = max over k in (i, j) of dp[i][k] + dp[k][j] + v[i] * v[k] * v[j]
Choosing the LAST operation rather than the first is what makes the halves independent, and it is the single most transferable idea in this topic.
## Padding with ones
Add a 1 at each end of the array. Then v[i] and v[j] are always real array entries and
the "missing neighbour counts as 1" rule needs no special case.
The answer is dp[0][n+1] on the padded array, the open interval containing everything.
## Why the intervals are open
dp[i][j] covers balloons strictly between i and j, so an interval of length 1, meaning
j = i + 1, contains nothing and scores 0. The loop therefore starts at length 2.
Mixing open and closed conventions halfway through is the usual source of an off-by-one here, and the symptom is a score that is too small by one product.
## Boundaries
A single balloon scores its own value times 1 times 1, so 5 answers 5 and 1 answers 1.
2 2 2 answers 14: burst the outer two first for 1*2*2 = 4 and 2*2*1 = 4, then the last
for 1*2*1 = 2. That is 10, so the best order is different, which is exactly why the input
is here.
## Cost
Time O(n^3). Space O(n^2).