What is Interval DP?
Interval DP is a dynamic programming pattern where you optimize over all sub-intervals of a range. The key idea: solve the smallest intervals first, then build up to the full range. This naturally leads to an O(n^3) template – O(n^2) sub-intervals, each requiring an O(n) scan over split points.
The core template:
for length in range(2, n+1):
for l in range(n - length + 1):
r = l + length - 1
for k in range(l, r):
dp[l][r] = min/max(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l, k, r))Key insight for all interval DP: Define what the last operation is – the last balloon burst, the last cut made, the last matrix multiplication. This transforms an exponential search into a polynomial recurrence.
Burst Balloons (LC 312)
Given an array of balloons with values, bursting balloon i gives coins nums[i-1] * nums[i] * nums[i+1]. Maximize total coins.
The trick: Think “last balloon to burst” instead of “first balloon to burst”. If balloon k is the last burst in interval [l, r], then when it bursts, l-1 and r+1 are still present (they are the boundaries). This gives a clean recurrence without cascading dependencies.
dp[l][r] = max coins from bursting all balloons strictly inside the padded interval [l, r].
def maxCoins(nums):
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for l in range(0, n - length):
r = l + length
for k in range(l + 1, r):
coins = nums[l] * nums[k] * nums[r]
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + coins)
return dp[0][n - 1]Time: O(n^3), Space: O(n^2).
Strange Printer (LC 664)
A printer can print a sequence of the same character in one turn, overwriting what was there. Find the minimum number of turns to print a given string.
Key insight: dp[i][j] = minimum turns to print s[i..j]. Base: dp[i][i] = 1. If s[i] == s[k] for some k in (i, j], we can extend the print of s[i] to also cover position k without an extra turn.
def strangePrinter(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
# Start with: print s[i] separately, then handle s[i+1..j]
dp[i][j] = 1 + dp[i + 1][j] if i + 1 <= j else 1
for k in range(i + 1, j + 1):
if s[k] == s[i]:
# Merge the turn for s[i] with the turn that prints s[k]
val = dp[i + 1][k] + dp[k][j] if i + 1 <= k else dp[k][j]
dp[i][j] = min(dp[i][j], val)
return dp[0][n - 1]Time: O(n^3), Space: O(n^2).
Minimum Cost to Cut a Stick (LC 1547)
A stick of length n with a set of required cut positions. The cost of a cut equals the current length of the stick being cut. Minimize total cost.
Setup: Add 0 and n to the cuts array and sort. dp[i][j] = min cost to make all cuts between cuts[i] and cuts[j]. The cost of making a cut at position cuts[k] within this segment is cuts[j] - cuts[i] (the current segment length).
def minCost(n, cuts):
cuts = sorted([0] + cuts + [n])
m = len(cuts)
dp = [[0] * m for _ in range(m)]
for length in range(2, m):
for i in range(m - length):
j = i + length
dp[i][j] = float('inf')
for k in range(i + 1, j):
cost = cuts[j] - cuts[i]
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost)
return dp[0][m - 1]Time: O(m^3) where m = len(cuts) + 2, Space: O(m^2).
Matrix Chain Multiplication (Classic)
Given matrices A1, A2, …, An where Ai has dimensions dims[i-1] x dims[i], find the parenthesization that minimizes total scalar multiplications.
dp[i][j] = min multiplications to compute the product of matrices i through j. Base: dp[i][i] = 0. Try all split points k in [i, j-1]: multiply (i..k) * (k+1..j), costing dims[i-1] * dims[k] * dims[j].
def matrixChain(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 = dims[i] * dims[k + 1] * dims[j + 1]
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost)
return dp[0][n - 1]Time: O(n^3), Space: O(n^2). This is the canonical interval DP problem – all others are variations on this structure.
Palindrome Partitioning III (LC 1278)
Split string s into exactly k non-overlapping palindromic substrings with minimum total character changes.
Precompute cost[i][j] = min changes to make s[i..j] a palindrome (use two-pointer: add 1 when s[l] != s[r]). Then dp[part][i] = min cost to split s[0..i] into part palindromes.
def palindromePartition(s, k):
n = len(s)
# cost[i][j] = min changes to make s[i..j] a palindrome
cost = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
cost[i][j] = cost[i+1][j-1] + (0 if s[i] == s[j] else 1)
# dp[part][i] = min cost to split s[0..i] into part palindromes
INF = float('inf')
dp = [[INF] * n for _ in range(k + 1)]
for i in range(n):
dp[1][i] = cost[0][i]
for part in range(2, k + 1):
for i in range(part - 1, n):
for j in range(part - 2, i):
if dp[part-1][j] < INF:
dp[part][i] = min(dp[part][i], dp[part-1][j] + cost[j+1][i])
return dp[k][n - 1]Time: O(k * n^2), Space: O(k * n).
The Universal Interval DP Template
Every interval DP problem maps onto this template:
# Step 1: Initialize dp table (usually 0 or INF depending on min/max)
dp = [[0] * n for _ in range(n)]
# Step 2: Fill by increasing interval length
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
dp[l][r] = float('inf') # or -inf for max problems
# Step 3: Try all split points
for k in range(l, r):
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l, k, r))Variations to watch for in interviews:
- Asymmetric split: Burst balloons uses
dp[l][k] + dp[k][r](k is not a split point but the last element) – adjust the loop bounds accordingly. - Precomputed cost: Matrix chain and stick cutting have O(1) cost functions. Palindrome partitioning precomputes a cost table first.
- Multiple dimensions: Palindrome Partitioning III adds a partition count dimension –
dp[parts][r]rather thandp[l][r]. - Bottom-up vs top-down: Both work. Top-down with memoization is often easier to implement correctly; bottom-up by length is more cache-friendly.
Meta coding interviews include interval DP patterns. See common questions for Meta interview: interval DP and optimization problems.
Databricks interviews include advanced DP patterns. See patterns for Databricks interview: dynamic programming and optimization.
Apple coding rounds include interval DP problems. See patterns for Apple interview: interval DP and sequence optimization.