Interval DP
Fill a triangular table by range length. Each range takes the cheapest split into two shorter ranges.
Interval DP: Merging adjacent piles
dp[0][1], length 2: split at 0: 0 + 0 + 5 = 5. Best is 5, splitting at 0: merge piles 0..0 and 1..1 last, paying their total 5.
Cost
- Best
- O(n^3)
- Average
- O(n^3)
- Worst
- O(n^3)
- Space
- O(n^2)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Interval DP covers these too, in the same run.