Lesson 32.2 · Advanced DP
Interval DP: Choose the Last Split
dp[i][j] = best answer for the range i..j, built from smaller ranges by trying every split point k. Fill by increasing length.
14 min
Think of it like this
Planning the order to demolish a row of buildings where each demolition's cost depends on its current neighbours. It's easier to think about which building goes last: then its neighbours are fixed (the ends of the range), and the left and right parts are independent.
1.The "last" trick
In Burst Balloons, bursting a balloon changes its neighbours, which makes "first" choices messy. Instead choose the balloon k burst last in the open interval (l, r): at that moment its neighbours are l and r, and the two sides were solved independently. dp[l][r] = max over k of dp[l][k] + dp[k][r] + a[l] × a[k] × a[r].
Cutting a stick works the same way: the first cut in a segment costs the segment's length and splits it into two independent segments.
Fill by increasing interval length so smaller ranges are ready. Time O(n³) for n split points.
Remember
- State: a range.
- Try every split; often the last action.
- Fill by length; O(n³).
Common mistakes
- Filling row by row from the top (sub-intervals not ready).