Two-dimensional Dynamic Programming
Tables over ranges
The state is a range, and the trick is choosing which element to think about last.
Key idea
Why the natural framing fails
Consider removing elements one at a time, where what an element is worth depends on its current neighbors. The obvious framing is to ask which to remove first.
That does not work. After the first removal the remaining elements have new neighbors, so the subproblem is not a clean range of the original and cannot be indexed by one.
Why it works
Ask which element is removed last
Turn it around. In a given range, consider which element is removed last. At that moment everything else in the range is gone, so its neighbors are exactly the elements just outside the range, which are fixed and known.
That makes the subproblem clean. Everything to its left is a range, everything to its right is a range, and neither interacts with the other because the last element sat between them the whole time.
So the state is a range, the choice is which element within it goes last, and the answer combines the two smaller ranges with the value of that final removal.
Key idea
Pad the ends so the neighbors always exist
The elements just outside the range may not exist at the array's edges. Adding a sentinel value at each end, chosen so it does not affect the arithmetic, removes every boundary case.
For a product, the identity is one. This is the same sentinel idea as U4's zero-height bar and U5's infinities: invent a value that makes the edge behave like the middle.
With the padding in place, every choice of which element goes last splits the range into two independent halves. Here are the choices for the whole range, with the two halves each one leaves behind.
Why it works
The range indexes are the boundaries, not the contents
best[left][right] means the best score obtainable from the elements strictly between those two positions, with both boundaries still present. The boundaries are not part of the range; they are its context.
That convention is what makes the recurrence clean, and it is also why the loops run over gaps rather than over start and end directly. Writing down whether your indexes are inclusive or exclusive, before the loops, saves a great deal of confusion here.
Gotcha
Fill by increasing range length
Each cell reads strictly smaller ranges, so the fill order must be by increasing length rather than by row or column. Iterating rows top to bottom would read ranges that have not been computed.
This is the same dependency rule as every other table in the unit, and interval tables are where it is least obvious. If an interval solution returns zeros, the fill order is the first thing to check.
Cost
Cost
There are about n squared ranges and each tries every element inside it, so O(n cubed) time and O(n squared) space.
Cubic sounds alarming and is fine for the small constraints these problems carry. Seeing n at most a few hundred is the signal that a cubic interval table is expected, which is the constraints-as-a-hint idea from Unit 0 again.
Why think about the last one?
In an interval table over removals, why is it easier to reason about which element is removed last rather than first?
Burst Balloons
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.