Sign in to watch this lesson
Advanced - Dynamic Programming Ā· 4:55
Interval DP
When the best answer for a row is built from the best answers for its contiguous pieces, the state is a segment [i, j] and the table fills in order of increasing length. We solve a two-player take-from-either-end game by storing the mover's advantage on each segment, read the optimal moves off the triangle, and then turn to the split form of interval DP, merging blocks at the cheapest cut with prefix sums, and see when its cubic cost is too much.
You will learn
- Recognise problems whose state is a contiguous segment [i, j] and write the recurrence from its trimmed or split sub-segments
- Fill an interval table in order of increasing length (or i descending, j ascending) and explain why i ascending with j inside reads uncomputed cells
- Solve two-player take-from-either-end games by storing the mover's total minus the opponent's total, and recover the first player's score as (sum + difference) / 2
- Write the split form dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + cost(i, j) with prefix sums, and judge from n whether O(n^3) is fast enough