Data Structures & AlgorithmsCommon DP Patterns

Common DP Patterns

LevelAdvanced

Duration90 mins

TopicCommon DP Patterns

1 / 4

Interval DP

The Art of Dividing and Conquering Intervals

Consider a seemingly simple question: given a sequence of matrices, what is the minimum number of scalar multiplications needed to compute their product? At first glance, you might think—just multiply them left to right. But matrix multiplication is associative, meaning the final result is the same regardless of how you parenthesize the expression. The cost, however, can vary dramatically depending on the order of operations.

This observation opens the door to one of the most elegant patterns in dynamic programming: Interval DP. In this paradigm, the state represents a contiguous subinterval of the input, and the solution for larger intervals is built by combining solutions from smaller, contained intervals. It's a pattern that appears across an astonishing variety of problems—from optimal parenthesization to game theory, from computational geometry to bioinformatics.

What You Will Learn

By the end of this page, you will:

• Understand the structural signature of Interval DP problems • Master the canonical Matrix Chain Multiplication problem • Solve the Burst Balloons problem using interval thinking • Recognize when O(n³) complexity is acceptable and optimal • Implement interval DP with both memoization and tabulation • Develop intuition for placing the 'split point' in interval problems

Understanding Interval DP

Interval DP is a specialized dynamic programming pattern where the state is defined by the boundaries of a contiguous subinterval within the input. Unlike 1D DP where state might be a single index dp[i], or 2D DP with independent indices dp[i][j], Interval DP uses dp[i][j] where i and j represent the left and right boundaries of a subinterval, and i ≤ j.

The Defining Characteristics:

Contiguity: The subproblem is always a contiguous portion of the original input—never scattered elements.
Boundary Representation: State dp[i][j] represents the optimal solution for elements from index i to index j (inclusive or exclusive, depending on convention).
Combining Subintervals: The solution for interval [i, j] is computed by trying all possible split points k where i ≤ k < j, combining solutions for [i, k] and [k+1, j].
Bottom-Up by Length: In tabulation, intervals are processed in order of increasing length—first length 1, then length 2, and so on—ensuring dependencies are satisfied.

The Split Point Intuition

Think of every interval problem as asking: 'Where should I make the final cut?' or 'What is the last operation performed on this interval?' The split point k represents this critical decision. By trying all possible split points, we exhaustively explore all ways to decompose the problem.

The General Recurrence Pattern:

For most interval DP problems, the recurrence follows this template:

dp[i][j] = optimize over k in [i, j-1] {
    dp[i][k] ⊕ dp[k+1][j] ⊕ cost(i, k, j)
}

Where:

optimize is typically min or max
⊕ represents problem-specific combination (often addition)
cost(i, k, j) is the cost of combining the two sub-solutions at split point k

Base Cases:

Single-element intervals dp[i][i] often have trivial optimal values (0 cost, no operation needed)
Empty intervals may or may not be meaningful depending on the problem

Interval DP vs Other DP Patterns
Characteristic	1D DP	2D Grid DP	Interval DP
State Meaning	Position i	Positions (i, j) in grid	Subinterval [i, j]
Typical Dimensions	O(n)	O(m × n)	O(n²) upper triangle
Dependencies	Previous indices	Adjacent cells	All contained intervals
Fill Order	Left to right	Row by row or diagonal	By interval length
Time Complexity	O(n)	O(m × n)	O(n²) to O(n³)
Example Problems	Fibonacci, House Robber	Grid Paths, LCS	MCM, Burst Balloons

Matrix Chain Multiplication — The Canonical Example

The Matrix Chain Multiplication (MCM) problem is the most famous Interval DP problem, serving as the canonical introduction to this pattern. Let's dissect it completely.

Problem Statement:

Given a chain of n matrices A₁, A₂, ..., Aₙ, where matrix Aᵢ has dimensions p[i-1] × p[i], find the minimum number of scalar multiplications required to compute the product A₁ × A₂ × ... × Aₙ.

Key Insight: Associativity Without Commutativity

Matrix multiplication is:

Associative: (A × B) × C = A × (B × C) — same result
Not commutative: A × B ≠ B × A in general

The associative property means we can parenthesize in any way without changing the result. But the computational cost varies wildly:

Example: Consider three matrices:

A₁: 10 × 100
A₂: 100 × 5
A₃: 5 × 50

Multiplying (A₁ × A₂) first:

A₁ × A₂ costs 10 × 100 × 5 = 5,000 operations → result is 10 × 5
Then × A₃ costs 10 × 5 × 50 = 2,500 operations
Total: 7,500 operations

Multiplying (A₂ × A₃) first:

A₂ × A₃ costs 100 × 5 × 50 = 25,000 operations → result is 100 × 50
Then A₁ × result costs 10 × 100 × 50 = 50,000 operations
Total: 75,000 operations

The first ordering is 10× more efficient! For longer chains, the difference can be exponential.

The Exponential Search Space

The number of ways to parenthesize n matrices is the (n-1)th Catalan number: C(n-1) = (2n-2)! / (n!(n-1)!). For n=10, there are 4,862 ways. For n=20, over 1.7 billion. Brute force is utterly infeasible; DP reduces this to O(n³).

Formulating the DP:

Let dp[i][j] = minimum cost to multiply matrices from Aᵢ to Aⱼ.

Base Case:

dp[i][i] = 0 — a single matrix requires no multiplication.

Recurrence:

For the subchain from i to j, we try every possible split point k where we compute Aᵢ...Aₖ separately from Aₖ₊₁...Aⱼ, then multiply the results:

dp[i][j] = min over k ∈ [i, j-1] {
    dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j]
}

The term p[i-1] × p[k] × p[j] is the cost of the final multiplication:

Left subproduct has dimensions p[i-1] × p[k]
Right subproduct has dimensions p[k] × p[j]
Multiplying them costs p[i-1] × p[k] × p[j]

Why This Works:

Any valid parenthesization has a last multiplication that splits the chain into two parts. By trying all possible positions for this last multiplication and recursing on both parts, we explore all parenthesizations.

matrix_chain_multiplication.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def matrix_chain_order(p: list[int]) -> int:
    """
    Find minimum number of scalar multiplications to multiply
    a chain of matrices with dimensions given by p.
    
    Matrix i has dimensions p[i-1] x p[i].
    So for n matrices, p has n+1 elements.
    
    Returns: Minimum number of scalar multiplications.
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    n = len(p) - 1  # Number of matrices
    
    if n == 0:
        return 0
    
    # dp[i][j] = min cost to multiply matrices i through j (1-indexed)
    # We'll use 1-indexed for matrices, so dp size is (n+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Base case: single matrix costs 0
    # dp[i][i] = 0 (already initialized)
    
    # Fill by increasing chain length
    for length in range(2, n + 1):  # length of chain
        for i in range(1, n - length + 2):  # start of chain
            j = i + length - 1  # end of chain
            dp[i][j] = float('inf')
            
            # Try all split points
            for k in range(i, j):
                # Cost = cost of left part + cost of right part + cost of final multiplication
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
 
 
def matrix_chain_with_solution(p: list[int]) -> tuple[int, str]:
    """
    Extended version that also returns the optimal parenthesization.
    """
    n = len(p) - 1
    
    if n == 0:
        return 0, ""
    if n == 1:
        return 0, "A1"
    
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]  # Records where to split
    
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k  # Remember the optimal split point
    
    def build_solution(i: int, j: int) -> str:
        if i == j:
            return f"A{i}"
        k = split[i][j]
        left = build_solution(i, k)
        right = build_solution(k + 1, j)
        return f"({left} × {right})"
    
    return dp[1][n], build_solution(1, n)
 
 
# Example usage
if __name__ == "__main__":
    # Dimensions: A1 is 10x100, A2 is 100x5, A3 is 5x50
    dimensions = [10, 100, 5, 50]
    
    min_cost = matrix_chain_order(dimensions)
    print(f"Minimum multiplications: {min_cost}")
    
    min_cost, parenthesization = matrix_chain_with_solution(dimensions)
    print(f"Optimal parenthesization: {parenthesization}")
    print(f"Total cost: {min_cost}")
    
    # Output:
    # Minimum multiplications: 7500
    # Optimal parenthesization: ((A1 × A2) × A3)
    # Total cost: 7500

Burst Balloons — Interval DP in Disguise

The Burst Balloons problem (LeetCode 312) is a masterclass in recognizing interval DP when it's not immediately obvious. It also demonstrates a crucial technique: thinking in reverse.

Problem Statement:

You have n balloons, indexed from 0 to n-1. Each balloon is painted with a number represented by array nums. You are asked to burst all balloons. If you burst balloon i, you will get nums[i-1] × nums[i] × nums[i+1] coins. After the burst, i-1 and i+1 become adjacent. Find the maximum coins you can collect.

Note: nums[-1] = nums[n] = 1 (virtual boundaries).

Example:

nums = [3, 1, 5, 8]
Optimal order: Burst 1 → 5 → 3 → 8
Coins: 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15 + 120 + 24 + 8 = 167

Why Is This Hard?

The naive approach thinks forward: 'Which balloon should I burst first?' But here's the problem—when you burst a balloon, the adjacencies change! The coin value for bursting balloon i depends on which neighbors are still present, which depends on the entire history of bursts. This seems to require tracking the full state of remaining balloons.

The Key Insight: Think Backwards

Instead of asking 'Which balloon do I burst FIRST in this interval?', ask 'Which balloon do I burst LAST?' If balloon k is the LAST to be burst in interval (i, j), then when we burst k, all other balloons in (i, j) are already gone. The neighbors of k are exactly i and j! This eliminates the dependency on burst history.

Reformulating with Interval DP:

Let dp[i][j] = maximum coins obtainable by bursting all balloons in the open interval (i, j), assuming balloons at positions i and j are not burst (they serve as boundaries).

We add virtual balloons: nums[-1] = 1 and nums[n] = 1.

Base Case:

dp[i][j] = 0 when j ≤ i + 1 (no balloons between i and j)

Recurrence:

For interval (i, j), try each balloon k in (i, j) as the last balloon to burst:

dp[i][j] = max over k ∈ (i+1, ..., j-1) {
    dp[i][k] + dp[k][j] + nums[i] × nums[k] × nums[j]
}

Understanding the Recurrence:

dp[i][k]: Maximum coins from bursting all balloons in (i, k) (before k)
dp[k][j]: Maximum coins from bursting all balloons in (k, j) (before k)
nums[i] × nums[k] × nums[j]: Coins when k is finally burst (neighbors are i and j, since everything else between i and j is gone)

The "reverse thinking" transforms a problem with complex state dependencies into clean interval DP!

burst_balloons.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def max_coins(nums: list[int]) -> int:
    """
    Find maximum coins by bursting all balloons optimally.
    
    Key insight: Think backwards - which balloon is burst LAST in each interval?
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    # Add virtual balloons at boundaries
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    # dp[i][j] = max coins from bursting all balloons in open interval (i, j)
    # Balloons i and j are boundaries, not to be burst in this subproblem
    dp = [[0] * n for _ in range(n)]
    
    # Process by interval length
    for length in range(2, n):  # length from 2 to n-1
        for i in range(n - length):
            j = i + length
            
            # Try each balloon k in (i, j) as the LAST one to burst
            for k in range(i + 1, j):
                # Coins from left, right, and bursting k last
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                dp[i][j] = max(dp[i][j], coins)
    
    # Answer is for interval (0, n-1), which is the entire original array
    return dp[0][n - 1]
 
 
def max_coins_with_order(nums: list[int]) -> tuple[int, list[int]]:
    """
    Extended version that also returns the optimal burst order.
    """
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    dp = [[0] * n for _ in range(n)]
    last = [[0] * n for _ in range(n)]  # Which balloon is burst last in (i, j)
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            
            for k in range(i + 1, j):
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
                    last[i][j] = k
    
    def reconstruct(i: int, j: int) -> list[int]:
        """Reconstruct burst order from the 'last' table."""
        if j <= i + 1:
            return []
        
        k = last[i][j]
        # First burst everything except k
        left_order = reconstruct(i, k)
        right_order = reconstruct(k, j)
        # Then burst k (converted back to 0-indexed original)
        return left_order + right_order + [k - 1]  # k-1 because we added boundary
    
    order = reconstruct(0, n - 1)
    return dp[0][n - 1], order
 
 
# Example
if __name__ == "__main__":
    nums = [3, 1, 5, 8]
    
    max_coins_value = max_coins(nums)
    print(f"Maximum coins: {max_coins_value}")
    
    max_coins_value, burst_order = max_coins_with_order(nums)
    print(f"Maximum coins: {max_coins_value}")
    print(f"Burst order (0-indexed): {burst_order}")
    
    # Verify: simulate the burst order
    remaining = list(nums)
    total = 0
    for idx in burst_order:
        # Find actual position after previous bursts
        left = remaining[idx - 1] if idx > 0 else 1
        right = remaining[idx + 1] if idx < len(remaining) - 1 else 1
        coins = left * remaining[idx] * right
        total += coins
        print(f"  Burst balloon {remaining[idx]} at position {idx}: {left}×{remaining[idx]}×{right} = {coins}")
        remaining.pop(idx)
    
    print(f"Total verified: {total}")

Optimal Binary Search Tree — Interval DP for Tree Construction

The Optimal Binary Search Tree (OBST) problem extends interval DP to tree construction. Given a sorted sequence of keys with known access frequencies, we want to build a BST that minimizes the expected search cost.

Problem Statement:

Given n sorted keys k₁ < k₂ < ... < kₙ with access probabilities p[1], p[2], ..., p[n], find the BST that minimizes:

Expected Cost = Σ (depth(kᵢ) + 1) × p[i]
              = Σ (level of kᵢ) × p[i]

Where level of root = 1, and each child is one level deeper.

Why Interval DP?

When we choose key kᵣ as the root of a subtree containing keys kᵢ to kⱼ:

Keys kᵢ, kᵢ₊₁, ..., kᵣ₋₁ go to the left subtree
Keys kᵣ₊₁, kᵣ₊₂, ..., kⱼ go to the right subtree

Both subtrees are contiguous intervals of the original sorted sequence! This is the hallmark of interval DP.

The Recurrence:

Let dp[i][j] = minimum expected cost for a BST containing keys kᵢ to kⱼ. Let w[i][j] = sum of probabilities p[i] + p[i+1] + ... + p[j].

Base Case:

dp[i][i] = p[i] (single key tree)
dp[i][i-1] = 0 (empty tree, for convenience)

Recurrence:

dp[i][j] = w[i][j] + min over r ∈ [i, j] {
    dp[i][r-1] + dp[r+1][j]
}

The w[i][j] term accounts for all keys in the subtree going one level deeper when attached under a root.

The Weight Term Explained

When we make kᵣ the root, all other keys in [i, j] become one level deeper. This adds w[i][j] - p[r] to the cost. But we also count p[r] for the root itself at level 1. Combined with the recursive costs (which already count depths relative to subtree roots), we get the elegant formula: cost = w[i][j] + cost(left subtree) + cost(right subtree).

optimal_bst.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def optimal_bst(keys: list, prob: list[float]) -> tuple[float, list[list[int]]]:
    """
    Find the optimal BST minimizing expected search cost.
    
    Args:
        keys: Sorted list of keys
        prob: prob[i] = access probability of keys[i]
    
    Returns:
        Tuple of (minimum expected cost, root table for reconstruction)
    
    Time Complexity: O(n³) - can be optimized to O(n²) using Knuth's optimization
    Space Complexity: O(n²)
    """
    n = len(keys)
    
    if n == 0:
        return 0.0, []
    
    # Precompute prefix sums for O(1) range sum queries
    prefix_sum = [0.0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + prob[i]
    
    def weight(i: int, j: int) -> float:
        """Sum of probabilities from index i to j (0-indexed, inclusive)."""
        if i > j:
            return 0.0
        return prefix_sum[j + 1] - prefix_sum[i]
    
    # dp[i][j] = min expected cost for keys[i..j]
    # Using n+2 size to handle boundary cases elegantly
    dp = [[0.0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 2)]
    
    # Base case: single keys
    for i in range(n):
        dp[i][i] = prob[i]
        root[i][i] = i
    
    # Fill by increasing length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            w = weight(i, j)
            
            # Try each key as root
            for r in range(i, j + 1):
                # Cost of left subtree (if exists)
                left_cost = dp[i][r - 1] if r > i else 0.0
                # Cost of right subtree (if exists)
                right_cost = dp[r + 1][j] if r < j else 0.0
                
                cost = w + left_cost + right_cost
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    root[i][j] = r
    
    return dp[0][n - 1], root
 
 
def print_optimal_bst(keys: list, root: list[list[int]], i: int, j: int, 
                      parent: str = "", direction: str = "Root"):
    """Recursively print the structure of the optimal BST."""
    if i > j:
        return
    
    r = root[i][j]
    if parent:
        print(f"  {keys[r]} is {direction} child of {parent}")
    else:
        print(f"  {keys[r]} is the Root")
    
    print_optimal_bst(keys, root, i, r - 1, keys[r], "left")
    print_optimal_bst(keys, root, r + 1, j, keys[r], "right")
 
 
# Example
if __name__ == "__main__":
    # Keys and their access frequencies
    keys = ['A', 'B', 'C', 'D', 'E']
    probabilities = [0.25, 0.20, 0.05, 0.20, 0.30]  # Must sum to 1
    
    min_cost, root_table = optimal_bst(keys, probabilities)
    
    print(f"Keys: {keys}")
    print(f"Probabilities: {probabilities}")
    print(f"Minimum expected search cost: {min_cost:.4f}")
    print(f"\nOptimal BST structure:")
    print_optimal_bst(keys, root_table, 0, len(keys) - 1)
    
    # The optimal BST might look quite different from a balanced tree
    # because frequently accessed keys should be near the root

Common Patterns and Problem Variations

Interval DP problems share recognizable signatures. Learning to spot these patterns accelerates your problem-solving ability.

Recognizing Interval DP Problems

•Sequential Operations on Arrays: Problems where you perform operations on a sequence and the operation's effect depends on neighbors or boundaries.
•Parenthesization/Grouping: Any problem about optimal ways to group or parenthesize a sequence (expressions, matrices, strings).
•Game Theory on Sequences: Two-player games where players take from ends or make choices over contiguous ranges.
•Merging/Splitting: Problems involving costs of merging adjacent elements (e.g., merging stones, file concatenation).
•Palindrome Construction: Building palindromes by considering what characters bracket the interval.
•Tree Construction from Sequences: Building optimal trees where subtrees correspond to subintervals.

Classic Interval DP Problems
Problem	State Meaning	Split Interpretation	Time
Matrix Chain Multiplication	Min cost for matrices i to j	Last multiplication position	O(n³)
Burst Balloons	Max coins in open interval (i,j)	Last balloon to burst	O(n³)
Optimal BST	Min expected cost for keys i to j	Root of subtree	O(n³)*
Minimum Score Triangulation	Min score for polygon vertices i to j	Third vertex of triangle with edge i-j	O(n³)
Palindrome Partitioning II	Min cuts for substring i to j	Position of last cut	O(n²)
Stone Game / Merge Stones	Min/max cost merging stones i to j	Where to split for final merge	O(n³)
Boolean Parenthesization	Ways to parenthesize for true/false	Position of outermost operator	O(n³)

The Three-Loop Structure

Almost all interval DP solutions in tabulation form have the same three-loop structure:

Outer loop: Iterate over interval lengths (from 1 or 2 up to n)
Middle loop: Iterate over starting positions i
Inner loop: Iterate over split points k within [i, j]

This gives O(n³) time. Recognize this structure, and implementing interval DP becomes mechanical.

Implementation Considerations and Optimizations

Tabulation vs Memoization:

Interval DP can be implemented both ways:

Tabulation (Bottom-Up):

Process intervals by increasing length
Explicit control over fill order
Slightly more cache-friendly
Easier to optimize space when possible

Memoization (Top-Down):

More intuitive for complex recurrences
Naturally handles sparse subproblem usage
Easier to add pruning conditions
Stack depth can be O(n), potentially causing overflow for large n

Common Pitfalls

•Off-by-one errors: Be crystal clear whether intervals are [i,j] or (i,j).
•Forgetting base cases: dp[i][i] and/or dp[i][i-1] need proper initialization.
•Wrong loop bounds: Ensure j = i + length - 1 doesn't exceed array bounds.
•Incorrect split range: k should typically go from i to j-1, not i to j.

Optimization Techniques

•Knuth's Optimization: For monotonic cost functions, reduces O(n³) to O(n²).
•Precompute costs: Use prefix sums for range sum queries.
•Space reduction: Sometimes only adjacent lengths needed.
•Early termination: In memoization, add pruning when possible.

Knuth's Optimization

For problems satisfying the quadrangle inequality (optimal split points are monotonic), Knuth's optimization constrains the search for optimal k. If opt[i][j] is the optimal split point:

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

This reduces the total inner loop iterations from O(n³) to O(n²). The Optimal BST problem can leverage this optimization.

Summary: Mastering Interval DP

Interval DP is a powerful pattern that elegantly handles problems involving contiguous subintervals. Let's consolidate the key insights:

Key Takeaways

•State represents intervals: dp[i][j] captures the optimal solution for the contiguous subinterval from index i to index j.
•Split point enumeration: The recurrence tries all ways to divide the interval into two smaller intervals, combining their solutions.
•Process by length: In tabulation, we fill the DP table in order of increasing interval length, ensuring dependencies are resolved.
•O(n³) is typical: Most interval DP solutions require O(n³) time due to the three nested loops (length, start, split).
•Think backwards when helpful: Problems like Burst Balloons become tractable by asking 'What is the LAST operation?' instead of 'What is the FIRST?'
•Applications are diverse: Matrix chain, optimal trees, game theory, polygon triangulation, and many string problems all use this pattern.

Page Complete

You now understand Interval DP—one of the most elegant and widely applicable DP patterns. The next page explores Bitmask DP, where we use binary representations to track which elements have been selected or processed, enabling efficient solutions for problems with small element counts but complex selection constraints.

1 / 4

Loading learning content...

Data Structures & AlgorithmsCommon DP Patterns

Common DP Patterns

LevelAdvanced

Duration90 mins

TopicCommon DP Patterns

1 / 4

Interval DP

The Art of Dividing and Conquering Intervals

What You Will Learn

By the end of this page, you will:

Understanding Interval DP

The Defining Characteristics:

Contiguity: The subproblem is always a contiguous portion of the original input—never scattered elements.
Boundary Representation: State dp[i][j] represents the optimal solution for elements from index i to index j (inclusive or exclusive, depending on convention).
Combining Subintervals: The solution for interval [i, j] is computed by trying all possible split points k where i ≤ k < j, combining solutions for [i, k] and [k+1, j].
Bottom-Up by Length: In tabulation, intervals are processed in order of increasing length—first length 1, then length 2, and so on—ensuring dependencies are satisfied.

The Split Point Intuition

The General Recurrence Pattern:

For most interval DP problems, the recurrence follows this template:

dp[i][j] = optimize over k in [i, j-1] {
    dp[i][k] ⊕ dp[k+1][j] ⊕ cost(i, k, j)
}

Where:

optimize is typically min or max
⊕ represents problem-specific combination (often addition)
cost(i, k, j) is the cost of combining the two sub-solutions at split point k

Base Cases:

Single-element intervals dp[i][i] often have trivial optimal values (0 cost, no operation needed)
Empty intervals may or may not be meaningful depending on the problem

Interval DP vs Other DP Patterns
Characteristic	1D DP	2D Grid DP	Interval DP
State Meaning	Position i	Positions (i, j) in grid	Subinterval [i, j]
Typical Dimensions	O(n)	O(m × n)	O(n²) upper triangle
Dependencies	Previous indices	Adjacent cells	All contained intervals
Fill Order	Left to right	Row by row or diagonal	By interval length
Time Complexity	O(n)	O(m × n)	O(n²) to O(n³)
Example Problems	Fibonacci, House Robber	Grid Paths, LCS	MCM, Burst Balloons

Matrix Chain Multiplication — The Canonical Example

The Matrix Chain Multiplication (MCM) problem is the most famous Interval DP problem, serving as the canonical introduction to this pattern. Let's dissect it completely.

Problem Statement:

Key Insight: Associativity Without Commutativity

Matrix multiplication is:

Associative: (A × B) × C = A × (B × C) — same result
Not commutative: A × B ≠ B × A in general

The associative property means we can parenthesize in any way without changing the result. But the computational cost varies wildly:

Example: Consider three matrices:

A₁: 10 × 100
A₂: 100 × 5
A₃: 5 × 50

Multiplying (A₁ × A₂) first:

A₁ × A₂ costs 10 × 100 × 5 = 5,000 operations → result is 10 × 5
Then × A₃ costs 10 × 5 × 50 = 2,500 operations
Total: 7,500 operations

Multiplying (A₂ × A₃) first:

A₂ × A₃ costs 100 × 5 × 50 = 25,000 operations → result is 100 × 50
Then A₁ × result costs 10 × 100 × 50 = 50,000 operations
Total: 75,000 operations

The first ordering is 10× more efficient! For longer chains, the difference can be exponential.

The Exponential Search Space

Formulating the DP:

Let dp[i][j] = minimum cost to multiply matrices from Aᵢ to Aⱼ.

Base Case:

dp[i][i] = 0 — a single matrix requires no multiplication.

Recurrence:

For the subchain from i to j, we try every possible split point k where we compute Aᵢ...Aₖ separately from Aₖ₊₁...Aⱼ, then multiply the results:

dp[i][j] = min over k ∈ [i, j-1] {
    dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j]
}

The term p[i-1] × p[k] × p[j] is the cost of the final multiplication:

Left subproduct has dimensions p[i-1] × p[k]
Right subproduct has dimensions p[k] × p[j]
Multiplying them costs p[i-1] × p[k] × p[j]

Why This Works:

matrix_chain_multiplication.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def matrix_chain_order(p: list[int]) -> int:
    """
    Find minimum number of scalar multiplications to multiply
    a chain of matrices with dimensions given by p.
    
    Matrix i has dimensions p[i-1] x p[i].
    So for n matrices, p has n+1 elements.
    
    Returns: Minimum number of scalar multiplications.
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    n = len(p) - 1  # Number of matrices
    
    if n == 0:
        return 0
    
    # dp[i][j] = min cost to multiply matrices i through j (1-indexed)
    # We'll use 1-indexed for matrices, so dp size is (n+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Base case: single matrix costs 0
    # dp[i][i] = 0 (already initialized)
    
    # Fill by increasing chain length
    for length in range(2, n + 1):  # length of chain
        for i in range(1, n - length + 2):  # start of chain
            j = i + length - 1  # end of chain
            dp[i][j] = float('inf')
            
            # Try all split points
            for k in range(i, j):
                # Cost = cost of left part + cost of right part + cost of final multiplication
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[1][n]
 
 
def matrix_chain_with_solution(p: list[int]) -> tuple[int, str]:
    """
    Extended version that also returns the optimal parenthesization.
    """
    n = len(p) - 1
    
    if n == 0:
        return 0, ""
    if n == 1:
        return 0, "A1"
    
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]  # Records where to split
    
    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k  # Remember the optimal split point
    
    def build_solution(i: int, j: int) -> str:
        if i == j:
            return f"A{i}"
        k = split[i][j]
        left = build_solution(i, k)
        right = build_solution(k + 1, j)
        return f"({left} × {right})"
    
    return dp[1][n], build_solution(1, n)
 
 
# Example usage
if __name__ == "__main__":
    # Dimensions: A1 is 10x100, A2 is 100x5, A3 is 5x50
    dimensions = [10, 100, 5, 50]
    
    min_cost = matrix_chain_order(dimensions)
    print(f"Minimum multiplications: {min_cost}")
    
    min_cost, parenthesization = matrix_chain_with_solution(dimensions)
    print(f"Optimal parenthesization: {parenthesization}")
    print(f"Total cost: {min_cost}")
    
    # Output:
    # Minimum multiplications: 7500
    # Optimal parenthesization: ((A1 × A2) × A3)
    # Total cost: 7500

Burst Balloons — Interval DP in Disguise

The Burst Balloons problem (LeetCode 312) is a masterclass in recognizing interval DP when it's not immediately obvious. It also demonstrates a crucial technique: thinking in reverse.

Problem Statement:

Note: nums[-1] = nums[n] = 1 (virtual boundaries).

Example:

nums = [3, 1, 5, 8]
Optimal order: Burst 1 → 5 → 3 → 8
Coins: 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15 + 120 + 24 + 8 = 167

Why Is This Hard?

The Key Insight: Think Backwards

Reformulating with Interval DP:

Let dp[i][j] = maximum coins obtainable by bursting all balloons in the open interval (i, j), assuming balloons at positions i and j are not burst (they serve as boundaries).

We add virtual balloons: nums[-1] = 1 and nums[n] = 1.

Base Case:

dp[i][j] = 0 when j ≤ i + 1 (no balloons between i and j)

Recurrence:

For interval (i, j), try each balloon k in (i, j) as the last balloon to burst:

dp[i][j] = max over k ∈ (i+1, ..., j-1) {
    dp[i][k] + dp[k][j] + nums[i] × nums[k] × nums[j]
}

Understanding the Recurrence:

dp[i][k]: Maximum coins from bursting all balloons in (i, k) (before k)
dp[k][j]: Maximum coins from bursting all balloons in (k, j) (before k)
nums[i] × nums[k] × nums[j]: Coins when k is finally burst (neighbors are i and j, since everything else between i and j is gone)

The "reverse thinking" transforms a problem with complex state dependencies into clean interval DP!

burst_balloons.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def max_coins(nums: list[int]) -> int:
    """
    Find maximum coins by bursting all balloons optimally.
    
    Key insight: Think backwards - which balloon is burst LAST in each interval?
    
    Time Complexity: O(n³)
    Space Complexity: O(n²)
    """
    # Add virtual balloons at boundaries
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    # dp[i][j] = max coins from bursting all balloons in open interval (i, j)
    # Balloons i and j are boundaries, not to be burst in this subproblem
    dp = [[0] * n for _ in range(n)]
    
    # Process by interval length
    for length in range(2, n):  # length from 2 to n-1
        for i in range(n - length):
            j = i + length
            
            # Try each balloon k in (i, j) as the LAST one to burst
            for k in range(i + 1, j):
                # Coins from left, right, and bursting k last
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                dp[i][j] = max(dp[i][j], coins)
    
    # Answer is for interval (0, n-1), which is the entire original array
    return dp[0][n - 1]
 
 
def max_coins_with_order(nums: list[int]) -> tuple[int, list[int]]:
    """
    Extended version that also returns the optimal burst order.
    """
    balloons = [1] + nums + [1]
    n = len(balloons)
    
    dp = [[0] * n for _ in range(n)]
    last = [[0] * n for _ in range(n)]  # Which balloon is burst last in (i, j)
    
    for length in range(2, n):
        for i in range(n - length):
            j = i + length
            
            for k in range(i + 1, j):
                coins = dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
                    last[i][j] = k
    
    def reconstruct(i: int, j: int) -> list[int]:
        """Reconstruct burst order from the 'last' table."""
        if j <= i + 1:
            return []
        
        k = last[i][j]
        # First burst everything except k
        left_order = reconstruct(i, k)
        right_order = reconstruct(k, j)
        # Then burst k (converted back to 0-indexed original)
        return left_order + right_order + [k - 1]  # k-1 because we added boundary
    
    order = reconstruct(0, n - 1)
    return dp[0][n - 1], order
 
 
# Example
if __name__ == "__main__":
    nums = [3, 1, 5, 8]
    
    max_coins_value = max_coins(nums)
    print(f"Maximum coins: {max_coins_value}")
    
    max_coins_value, burst_order = max_coins_with_order(nums)
    print(f"Maximum coins: {max_coins_value}")
    print(f"Burst order (0-indexed): {burst_order}")
    
    # Verify: simulate the burst order
    remaining = list(nums)
    total = 0
    for idx in burst_order:
        # Find actual position after previous bursts
        left = remaining[idx - 1] if idx > 0 else 1
        right = remaining[idx + 1] if idx < len(remaining) - 1 else 1
        coins = left * remaining[idx] * right
        total += coins
        print(f"  Burst balloon {remaining[idx]} at position {idx}: {left}×{remaining[idx]}×{right} = {coins}")
        remaining.pop(idx)
    
    print(f"Total verified: {total}")

Optimal Binary Search Tree — Interval DP for Tree Construction

Problem Statement:

Given n sorted keys k₁ < k₂ < ... < kₙ with access probabilities p[1], p[2], ..., p[n], find the BST that minimizes:

Expected Cost = Σ (depth(kᵢ) + 1) × p[i]
              = Σ (level of kᵢ) × p[i]

Where level of root = 1, and each child is one level deeper.

Why Interval DP?

When we choose key kᵣ as the root of a subtree containing keys kᵢ to kⱼ:

Keys kᵢ, kᵢ₊₁, ..., kᵣ₋₁ go to the left subtree
Keys kᵣ₊₁, kᵣ₊₂, ..., kⱼ go to the right subtree

Both subtrees are contiguous intervals of the original sorted sequence! This is the hallmark of interval DP.

The Recurrence:

Let dp[i][j] = minimum expected cost for a BST containing keys kᵢ to kⱼ. Let w[i][j] = sum of probabilities p[i] + p[i+1] + ... + p[j].

Base Case:

dp[i][i] = p[i] (single key tree)
dp[i][i-1] = 0 (empty tree, for convenience)

Recurrence:

dp[i][j] = w[i][j] + min over r ∈ [i, j] {
    dp[i][r-1] + dp[r+1][j]
}

The w[i][j] term accounts for all keys in the subtree going one level deeper when attached under a root.

The Weight Term Explained

optimal_bst.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def optimal_bst(keys: list, prob: list[float]) -> tuple[float, list[list[int]]]:
    """
    Find the optimal BST minimizing expected search cost.
    
    Args:
        keys: Sorted list of keys
        prob: prob[i] = access probability of keys[i]
    
    Returns:
        Tuple of (minimum expected cost, root table for reconstruction)
    
    Time Complexity: O(n³) - can be optimized to O(n²) using Knuth's optimization
    Space Complexity: O(n²)
    """
    n = len(keys)
    
    if n == 0:
        return 0.0, []
    
    # Precompute prefix sums for O(1) range sum queries
    prefix_sum = [0.0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + prob[i]
    
    def weight(i: int, j: int) -> float:
        """Sum of probabilities from index i to j (0-indexed, inclusive)."""
        if i > j:
            return 0.0
        return prefix_sum[j + 1] - prefix_sum[i]
    
    # dp[i][j] = min expected cost for keys[i..j]
    # Using n+2 size to handle boundary cases elegantly
    dp = [[0.0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 2)]
    
    # Base case: single keys
    for i in range(n):
        dp[i][i] = prob[i]
        root[i][i] = i
    
    # Fill by increasing length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            w = weight(i, j)
            
            # Try each key as root
            for r in range(i, j + 1):
                # Cost of left subtree (if exists)
                left_cost = dp[i][r - 1] if r > i else 0.0
                # Cost of right subtree (if exists)
                right_cost = dp[r + 1][j] if r < j else 0.0
                
                cost = w + left_cost + right_cost
                
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    root[i][j] = r
    
    return dp[0][n - 1], root
 
 
def print_optimal_bst(keys: list, root: list[list[int]], i: int, j: int, 
                      parent: str = "", direction: str = "Root"):
    """Recursively print the structure of the optimal BST."""
    if i > j:
        return
    
    r = root[i][j]
    if parent:
        print(f"  {keys[r]} is {direction} child of {parent}")
    else:
        print(f"  {keys[r]} is the Root")
    
    print_optimal_bst(keys, root, i, r - 1, keys[r], "left")
    print_optimal_bst(keys, root, r + 1, j, keys[r], "right")
 
 
# Example
if __name__ == "__main__":
    # Keys and their access frequencies
    keys = ['A', 'B', 'C', 'D', 'E']
    probabilities = [0.25, 0.20, 0.05, 0.20, 0.30]  # Must sum to 1
    
    min_cost, root_table = optimal_bst(keys, probabilities)
    
    print(f"Keys: {keys}")
    print(f"Probabilities: {probabilities}")
    print(f"Minimum expected search cost: {min_cost:.4f}")
    print(f"\nOptimal BST structure:")
    print_optimal_bst(keys, root_table, 0, len(keys) - 1)
    
    # The optimal BST might look quite different from a balanced tree
    # because frequently accessed keys should be near the root

Common Patterns and Problem Variations

Interval DP problems share recognizable signatures. Learning to spot these patterns accelerates your problem-solving ability.

Recognizing Interval DP Problems

•Sequential Operations on Arrays: Problems where you perform operations on a sequence and the operation's effect depends on neighbors or boundaries.
•Parenthesization/Grouping: Any problem about optimal ways to group or parenthesize a sequence (expressions, matrices, strings).
•Game Theory on Sequences: Two-player games where players take from ends or make choices over contiguous ranges.
•Merging/Splitting: Problems involving costs of merging adjacent elements (e.g., merging stones, file concatenation).
•Palindrome Construction: Building palindromes by considering what characters bracket the interval.
•Tree Construction from Sequences: Building optimal trees where subtrees correspond to subintervals.

Classic Interval DP Problems
Problem	State Meaning	Split Interpretation	Time
Matrix Chain Multiplication	Min cost for matrices i to j	Last multiplication position	O(n³)
Burst Balloons	Max coins in open interval (i,j)	Last balloon to burst	O(n³)
Optimal BST	Min expected cost for keys i to j	Root of subtree	O(n³)*
Minimum Score Triangulation	Min score for polygon vertices i to j	Third vertex of triangle with edge i-j	O(n³)
Palindrome Partitioning II	Min cuts for substring i to j	Position of last cut	O(n²)
Stone Game / Merge Stones	Min/max cost merging stones i to j	Where to split for final merge	O(n³)
Boolean Parenthesization	Ways to parenthesize for true/false	Position of outermost operator	O(n³)

The Three-Loop Structure

Almost all interval DP solutions in tabulation form have the same three-loop structure:

Outer loop: Iterate over interval lengths (from 1 or 2 up to n)
Middle loop: Iterate over starting positions i
Inner loop: Iterate over split points k within [i, j]

This gives O(n³) time. Recognize this structure, and implementing interval DP becomes mechanical.

Implementation Considerations and Optimizations

Tabulation vs Memoization:

Interval DP can be implemented both ways:

Tabulation (Bottom-Up):

Process intervals by increasing length
Explicit control over fill order
Slightly more cache-friendly
Easier to optimize space when possible

Memoization (Top-Down):

More intuitive for complex recurrences
Naturally handles sparse subproblem usage
Easier to add pruning conditions
Stack depth can be O(n), potentially causing overflow for large n

Common Pitfalls

•Off-by-one errors: Be crystal clear whether intervals are [i,j] or (i,j).
•Forgetting base cases: dp[i][i] and/or dp[i][i-1] need proper initialization.
•Wrong loop bounds: Ensure j = i + length - 1 doesn't exceed array bounds.
•Incorrect split range: k should typically go from i to j-1, not i to j.

Optimization Techniques

•Knuth's Optimization: For monotonic cost functions, reduces O(n³) to O(n²).
•Precompute costs: Use prefix sums for range sum queries.
•Space reduction: Sometimes only adjacent lengths needed.
•Early termination: In memoization, add pruning when possible.

Knuth's Optimization

For problems satisfying the quadrangle inequality (optimal split points are monotonic), Knuth's optimization constrains the search for optimal k. If opt[i][j] is the optimal split point:

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

This reduces the total inner loop iterations from O(n³) to O(n²). The Optimal BST problem can leverage this optimization.

Summary: Mastering Interval DP

Interval DP is a powerful pattern that elegantly handles problems involving contiguous subintervals. Let's consolidate the key insights:

Key Takeaways

•State represents intervals: dp[i][j] captures the optimal solution for the contiguous subinterval from index i to index j.
•Split point enumeration: The recurrence tries all ways to divide the interval into two smaller intervals, combining their solutions.
•Process by length: In tabulation, we fill the DP table in order of increasing interval length, ensuring dependencies are resolved.
•O(n³) is typical: Most interval DP solutions require O(n³) time due to the three nested loops (length, start, split).
•Think backwards when helpful: Problems like Burst Balloons become tractable by asking 'What is the LAST operation?' instead of 'What is the FIRST?'
•Applications are diverse: Matrix chain, optimal trees, game theory, polygon triangulation, and many string problems all use this pattern.

Page Complete

1 / 4