AlgoScope

Interval DP

Fill a triangular table by range length. Each range takes the cheapest split into two shorter ranges.

Dynamic programming, technique, advanced
dp 0 1 is 5.4123412305000
dp 0 1 is 5.4123412305000

Interval DP: Merging adjacent piles

Decision, step 2 of 8

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.

How interval dp works

Cost

Best
O(n^3)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)

Leads to

Topics that need this one first.

Taught by the same lesson

Interval DP covers these too, in the same run.