AdvancedDynamic Programming

Interval DP

DP on intervals by choosing the last/first action inside a range

Time: O(n^3)
Space: O(n^2)
Pattern Overview

Core Idea

Define dp[l][r] and split at k in (l..r); often think 'burst last' to fix boundaries.

When to Use

Use when subproblems are contiguous ranges and choices partition the interval.

General Recognition Cues
General indicators that this pattern might be applicable
  • Range [l,r] decisions
  • Split point k
  • Associative cost
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Burst Balloons

Burst last to fix neighbors

When to Use This Variant
  • Neighbors fixed outside
Use Case
Max coins
Advantages
  • Avoids dependency cycles
Implementation
def burst_balloons(nums):
    nums=[1]+nums+[1]; n=len(nums)
    dp=[[0]*n for _ in range(n)]
    for len_ in range(2, n):
        for l in range(0, n-len_):
            r=l+len_
            for k in range(l+1, r):
                dp[l][r]=max(dp[l][r], nums[l]*nums[k]*nums[r]+dp[l][k]+dp[k][r])
    return dp[0][n-1]
2

Matrix Chain

Parenthesize to minimize multiplications

When to Use This Variant
  • Split point k
Use Case
Min cost
Advantages
  • Classic interval DP
Implementation
def matrix_chain(dims):
    n=len(dims)-1; dp=[[0]*n for _ in range(n)]
    for len_ in range(2, n+1):
        for l in range(0, n-len_+1):
            r=l+len_-1; dp[l][r]=10**18
            for k in range(l, r):
                dp[l][r]=min(dp[l][r], dp[l][k]+dp[k+1][r]+dims[l]*dims[k+1]*dims[r+1])
    return dp[0][n-1]
3

Merge Stones

Merge cost with window sizes

When to Use This Variant
  • k merges
Use Case
Min cost merge
Advantages
  • Careful feasibility
Implementation
def merge_stones(stones, K):
    n=len(stones); INF=10**18
    if (n-1)%(K-1)!=0: return -1
    pref=[0];
    for x in stones: pref.append(pref[-1]+x)
    dp=[[0]*n for _ in range(n)]
    for len_ in range(K, n+1):
        for l in range(0, n-len_+1):
            r=l+len_-1; dp[l][r]=INF
            for m in range(l, r, K-1):
                dp[l][r]=min(dp[l][r], dp[l][m]+dp[m+1][r])
            if (len_-1)%(K-1)==0:
                dp[l][r]+= pref[r+1]-pref[l]
    return dp[0][n-1]
Common Pitfalls
Watch out for these common mistakes
  • Iteration order (len increasing)
  • Double counting
  • Handling boundaries/padding
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n^3)

Split over k for each interval.

Space Complexity
O(n^2)

2D DP table.

Ready to test your knowledge?

Test your pattern recognition with interactive questions