13.11 Interval Dynamic Programming

Most dynamic programming problems decompose a problem into prefixes, suffixes, positions, or capacities. Interval dynamic programming takes a different approach. Instead of asking questions about a single position or prefix, it asks questions about contiguous ranges.

The central idea is simple:

A large interval can often be solved by combining solutions from smaller intervals.

This pattern appears in matrix chain multiplication, optimal binary search trees, palindrome transformations, burst balloons, polygon triangulation, expression evaluation, and many game-theoretic problems. Once you recognize interval structure, seemingly difficult optimization problems often become manageable.

Interval dynamic programming is also the first major example where the order of computation becomes more interesting. Unlike one-dimensional and many two-dimensional problems, states cannot simply be processed from left to right. Instead, intervals must be computed in order of increasing length.

Problem

How do we solve optimization problems whose natural subproblems are contiguous ranges?

Understanding Interval States

The defining characteristic of interval dynamic programming is a state of the form:

$$ dp[l][r] $$

Meaning:

The optimal solution for the interval from position (l) to position (r).

For example:

A B C D E

Possible states include:

[A]
[B]
[C]

[A,B]
[B,C]
[C,D]

[A,B,C]
[B,C,D]

...

Every state represents a contiguous segment of the original input.

Why Intervals Matter

Consider a sequence:

A B C D

Suppose an optimal solution requires splitting the sequence at some position:

A B | C D

The left side becomes one subproblem.

The right side becomes another.

This naturally suggests:

$$ dp[l][r] $$

states and recursive decomposition.

Many interval problems share this structure.

Example: Matrix Chain Multiplication

Suppose we want to compute:

A × B × C × D

Matrix multiplication is associative:

(A×B)×(C×D)

and:

((A×B)×C)×D

produce the same result.

However, they may require dramatically different numbers of operations.

The goal is to find the cheapest parenthesization.

State Design

Define:

$$ dp[l][r] $$

as:

The minimum cost of multiplying matrices from (l) through (r).

For example:

$$ dp[2][5] $$

asks:

minimum multiplication cost
for matrices 2 through 5

This mirrors the original problem on a smaller interval.

Understanding the Split Point

Every interval must eventually be split.

Suppose:

$$ [l,r] $$

is divided at:

$$ k $$

Then:

left interval:
[l,k]

right interval:
[k+1,r]

Both become smaller subproblems.

The total cost becomes:

$$ dp[l][k] + dp[k+1][r] + mergeCost $$

The optimal split is unknown.

Therefore all possible split points must be examined.

Matrix Chain Recurrence

The recurrence becomes:

$$ dp[l][r] = \min_{l \le k < r} \Big( dp[l][k] + dp[k+1][r] + cost(l,k,r) \Big) $$

This is the canonical interval DP recurrence.

Three components appear:

• left interval
• right interval
• merge cost

Many interval algorithms share this exact structure.

Base Cases

Intervals of length one require no work.

A single matrix is already multiplied.

Therefore:

$$ dp[i][i]=0 $$

This serves as the foundation of the computation.

Why Length Matters

Consider:

$$ dp[1][4] $$

Its recurrence depends on:

$$ dp[1][1] $$

$$ dp[2][4] $$

$$ dp[1][2] $$

$$ dp[3][4] $$

and so on.

Notice:

every dependency
has smaller interval length

This observation determines the computation order.

Computing by Increasing Length

The standard pattern is:

for length := 2; length <= n; length++ {
    ...
}

For each length:

for left := 0; left+length-1 < n; left++ {
    right := left + length - 1
}

This guarantees all smaller intervals have already been computed.

The resulting dependency structure is one of the defining characteristics of interval DP.

Example: Matrix Chain Multiplication

Suppose matrix dimensions are:

10×30
30×5
5×60

Two parenthesizations exist.

First Option

(A×B)×C

Cost:

$$ 10 \times 30 \times 5 + 10 \times 5 \times 60 = 4500 $$

Second Option

A×(B×C)

Cost:

$$ 30 \times 5 \times 60 + 10 \times 30 \times 60 = 27000 $$

The difference is substantial.

Dynamic programming systematically explores every valid split and chooses the cheapest.

Generic Interval Pattern

Many interval recurrences follow:

$$ dp[l][r] = \min \Big( dp[l][k] + dp[k+1][r] + cost \Big) $$

or:

$$ dp[l][r] = \max \Big( dp[l][k] + dp[k+1][r] + value \Big) $$

The split position:

$$ k $$

becomes the decision variable.

Example: Optimal Binary Search Tree

Suppose keys have different access frequencies.

The root can be chosen at any position.

Choosing root:

$$ k $$

creates:

left subtree
right subtree

which are themselves interval problems.

The recurrence closely resembles matrix chain multiplication.

Only the cost function changes.

This illustrates an important principle:

Many interval problems differ only in their merge cost.

Example: Burst Balloons

Given:

3 1 5 8

Bursting a balloon yields value based on neighboring balloons.

A useful observation is to reverse the thinking.

Instead of asking:

which balloon is burst first?

ask:

which balloon is burst last?

The final balloon divides the interval into independent subproblems.

This transformation converts a difficult problem into a standard interval DP.

Many advanced interval problems rely on similar perspective shifts.

Example: Palindrome Insertions

Problem:

minimum insertions
to form a palindrome

State:

$$ dp[l][r] $$

Meaning:

minimum insertions
for substring [l,r]

If characters match:

$$ dp[l][r] = dp[l+1][r-1] $$

Otherwise:

$$ dp[l][r] = 1 + \min ( dp[l+1][r], dp[l][r-1] ) $$

Notice that not every interval problem requires a split point.

Some intervals shrink inward instead.

The interval state remains the same.

Implementation Template

Most interval DP algorithms follow a common structure.

for length := 1; length <= n; length++ {

    for left := 0; left+length-1 < n; left++ {

        right := left + length - 1

        // compute dp[left][right]
    }
}

This pattern appears repeatedly throughout advanced dynamic programming.

Visualizing Dependencies

Imagine the DP table:

	0	1	2	3
0	•	•	•	•
1		•	•	•
2			•	•
3				•

The diagonal:

$$ dp[i][i] $$

contains base cases.

Longer intervals appear above the diagonal.

Computation proceeds diagonally upward:

length 1

length 2

length 3

length 4

This visualization is often helpful when debugging interval algorithms.

Common Mistakes

Incorrect Length Ordering

Processing large intervals before small intervals violates dependencies.

Always compute shorter intervals first.

Missing Split Positions

The recurrence usually requires:

$$ l \le k < r $$

Every possible split must be examined.

Ignoring one split may miss the optimal solution.

Wrong Base Cases

Many interval problems use:

$$ dp[i][i]=0 $$

Others use:

$$ dp[i][i]=1 $$

depending on state meaning.

Derive the base case directly from the state definition.

Off-by-One Errors

Interval algorithms are particularly susceptible to indexing mistakes.

Draw the interval boundaries explicitly during development.

Complexity Analysis

State count:

$$ O(n^2) $$

For each interval, every split point may be examined:

$$ O(n) $$

Total running time:

$$ O(n^3) $$

Memory usage:

$$ O(n^2) $$

This complexity appears frequently in interval dynamic programming.

Later chapters will introduce optimizations that reduce the cubic factor for specific classes of recurrences.

Recognizing Interval Dynamic Programming

Strong indicators include:

• contiguous ranges
• substring optimization
• interval merging
• parenthesization
• partitioning
• triangulation
• game ranges
• palindrome transformations

Whenever a problem can be expressed as:

solve interval [l,r]
using smaller intervals

interval dynamic programming should be considered.

Takeaway

Interval dynamic programming organizes subproblems around contiguous ranges rather than positions or prefixes. The defining state, (dp[l][r]), captures the optimal solution for a segment of the input, while recurrences typically split intervals into smaller independent subproblems. The resulting algorithms often require (O(n^2)) states and (O(n^3)) time, but they provide elegant solutions to problems involving parenthesization, partitioning, string transformations, and sequence optimization. Understanding interval dynamic programming is an important milestone because many advanced optimization techniques build directly on its recurrence structure.