Interval DP Pattern and Fill Order
Define the interval DP state dp[i][j], explain why intervals must be filled in increasing length order, and trace the pattern on matrix chain multiplication.
Interval DP Pattern and Fill Order is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is Interval DP?
Interval DP is a dynamic programming pattern where the state dp[i][j] represents the optimal answer for the sub-problem spanning indices i through j. The key insight is that we solve smaller intervals first and build up to the full range. This pattern naturally models problems like matrix chain multiplication, palindrome partitioning, and balloon bursting, where the sub-problem boundaries are the left and right endpoints of a range.
State Definition and Base Cases
For interval DP, the state is dp[i][j] where i <= j. The base cases are single-element intervals: dp[i][i]. These are trivially solved — for example, a single matrix has zero multiplication cost. Two-element intervals dp[i][i+1] often have simple answers too. We fill the table for increasing interval lengths, starting from length 1 up to n.
n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
dp[i][i] = 0 # length-1 intervalsFill Order: Increasing Length
The critical detail in interval DP is fill order. We must compute all intervals of length L before computing intervals of length L+1, because a longer interval depends on shorter sub-intervals. The outer loop iterates over the interval length from 2 to n, the middle loop sets the left boundary i, and we derive the right boundary as j = i + L - 1.
n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 0
for length in range(2, n + 1): # interval length
for i in range(n - length + 1): # left boundary
j = i + length - 1 # right boundary
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])Matrix Chain Multiplication Setup
The classic interval DP problem is matrix chain multiplication: given matrices with dimensions dims[0..n], find the minimum scalar multiplications to compute the product. Multiplying matrix A(p×q) by B(q×r) costs p*q*r operations. dp[i][j] = minimum cost to multiply matrices i through j. The split point k decides where the sequence is split into two sub-chains.
def matrix_chain_order(dims):
n = len(dims) - 1 # number of matrices
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
print(matrix_chain_order([10, 30, 5, 60])) # 4500Tracing the DP Table
Let's trace through the matrix chain example with dimensions [10, 30, 5, 60] representing three matrices: A(10×30), B(30×5), C(5×60). For dp[0][2] we try split at k=0: dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000, and at k=1: dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500. So dp[0][2] = 4500, achieved by multiplying AB first.
Why This Fill Order Works
When computing dp[i][j] we reference dp[i][k] and dp[k+1][j] for all k in [i, j-1]. Both sub-intervals have strictly smaller length than [i, j]. By iterating length from small to large, all required sub-intervals are computed before we need them. This is the fundamental correctness argument for interval DP fill order — shorter intervals are always dependencies of longer ones.
Memoised Top-Down Interval DP
Alternatively, interval DP can be implemented top-down with memoisation. We write a recursive function solve(i, j) that returns the optimal cost for interval [i, j], and cache results in a dictionary. The fill order is handled automatically by recursion. Top-down is often easier to reason about but may have function-call overhead; bottom-up is faster in practice for large inputs.
from functools import lru_cache
def matrix_chain_memo(dims):
n = len(dims) - 1
@lru_cache(maxsize=None)
def solve(i, j):
if i == j:
return 0
return min(
solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
for k in range(i, j)
)
return solve(0, n-1)
print(matrix_chain_memo([10, 30, 5, 60])) # 4500Time and Space Complexity
Interval DP has O(n²) states (all pairs (i, j)) and each state iterates over O(n) split points, giving O(n³) time overall. Space is O(n²) for the DP table. For matrix chain multiplication with 100 matrices, this is 1,000,000 operations — very feasible. The pattern appears in many hard LeetCode problems and is a favourite in FAANG interviews due to its non-obvious structure.
Reconstructing the Optimal Solution
To reconstruct the actual parenthesisation (not just the cost), store a separate split[i][j] table recording which k achieved the minimum at each state. Then recursively read off the splits: reconstruct(i, j) prints the optimal grouping by recursing on [i, split[i][j]] and [split[i][j]+1, j]. This technique applies to all interval DP problems.
def matrix_chain_with_split(dims):
n = len(dims) - 1
dp = [[0]*n for _ in range(n)]
split = [[0]*n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
return dp[0][n-1], splitTemplate for Any Interval DP Problem
The universal interval DP template has three parts: (1) initialise base cases for single elements, (2) loop over increasing lengths and for each length loop over valid left boundaries, computing the right boundary, and (3) for each interval iterate over all split points and apply the problem-specific recurrence. The only thing that changes between problems is the recurrence formula inside the innermost loop.
def interval_dp_template(n, base_cost, split_cost):
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
dp[i][i] = base_cost(i) # problem-specific base case
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
# problem-specific recurrence
candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
dp[i][j] = min(dp[i][j], candidate)
return dp[0][n-1]Common Interval DP Problems
Problems that use interval DP include: Matrix Chain Multiplication (minimise operations), Burst Balloons (maximise coins), Strange Printer (minimise print operations), Minimum Score Triangulation of Polygon, and Palindrome Partitioning II. Each uses the same fill-order skeleton but different recurrences. Recognise the pattern when a problem asks for an optimal value over a range or sequence that can be split at any interior point.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: interval DP uses dp[i][j] to represent the optimal answer over a range, fill order must be increasing interval length so sub-intervals are computed first, and the universal template has O(n³) time and O(n²) space. Next up we explore the longest palindromic subsequence and substring using this very pattern.
Frequently asked questions
Is the “Interval DP Pattern and Fill Order” lesson free?
Yes — the full text of “Interval DP Pattern and Fill Order” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Interval DP Pattern and Fill Order”?
Define the interval DP state dp[i][j], explain why intervals must be filled in increasing length order, and trace the pattern on matrix chain multiplication. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Interval DP Pattern and Fill Order” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Interval DP Pattern and Fill Order
- Longest Palindromic Subsequence and Substring
- Palindrome Partitioning II
- Burst Balloons: Reverse Interval DP