Interval DP and Advanced Dynamic Programming Patterns
Interval DP solves optimization problems over contiguous subarrays or subsequences. The core idea: the optimal solution for an interval [i, j] depends on solutions for smaller intervals within it. This guide covers interval DP and the other advanced DP patterns that appear in senior-level interviews.
Interval DP Template
Process all intervals of length 2, 3, …, n. For each interval [i, j], try all split points k and combine solutions for [i, k] and [k+1, j]:
n = len(arr)
dp = [[0] * n for _ in range(n)]
# Base case: intervals of length 1
for i in range(n):
dp[i][i] = base_value(i)
# Fill for increasing lengths
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf') # or -inf for max problems
for k in range(i, j): # try all split points
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, k, j))
return dp[0][n-1]Burst Balloons (LeetCode 312)
Pop all balloons to maximize coins. If you pop balloon k last in interval [i, j], it is surrounded by the boundary balloons (not yet popped):
def max_coins(nums):
nums = [1] + nums + [1] # add boundary sentinels
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n):
for left in range(n - length):
right = left + length
for k in range(left + 1, right): # k is the LAST balloon popped in [left, right]
coins = nums[left] * nums[k] * nums[right]
dp[left][right] = max(dp[left][right],
dp[left][k] + coins + dp[k][right])
return dp[0][n-1]
# Key insight: think "last balloon popped" not "first" — avoids tracking remaining balloonsMinimum Cost to Cut a Stick (LeetCode 1547)
def min_cost(n, cuts):
cuts = [0] + sorted(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):
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k][j] + cuts[j] - cuts[i])
return dp[0][m-1]Longest Palindromic Subsequence (LeetCode 516)
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n): dp[i][i] = 1 # single char is palindrome
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]State Machine DP
Model problems where the state changes based on actions. Classic: Best Time to Buy and Sell Stock with Cooldown (LeetCode 309):
def max_profit(prices):
# States: hold (own stock), sold (just sold, cooldown), rest (can buy)
hold = float('-inf') # max profit while holding
sold = 0 # max profit day after selling (cooldown)
rest = 0 # max profit while resting (can buy)
for price in prices:
prev_hold, prev_sold, prev_rest = hold, sold, rest
hold = max(prev_hold, prev_rest - price) # buy or keep holding
sold = prev_hold + price # sell
rest = max(prev_rest, prev_sold) # rest or come off cooldown
return max(sold, rest)DP on Trees
# Diameter of Binary Tree (LeetCode 543):
def diameter_of_binary_tree(root):
self.ans = 0
def depth(node):
if not node: return 0
l = depth(node.left)
r = depth(node.right)
self.ans = max(self.ans, l + r) # path through this node
return max(l, r) + 1
depth(root)
return self.ans
# House Robber III — cannot rob adjacent nodes (LeetCode 337):
def rob(root):
def dp(node):
if not node: return 0, 0 # (rob_node, skip_node)
l_rob, l_skip = dp(node.left)
r_rob, r_skip = dp(node.right)
rob_node = node.val + l_skip + r_skip
skip_node = max(l_rob, l_skip) + max(r_rob, r_skip)
return rob_node, skip_node
return max(dp(root))Digit DP
Count numbers in range [0, N] satisfying a digit-based constraint (e.g., no two consecutive equal digits):
def count_numbers(n):
digits = list(str(n))
from functools import lru_cache
@lru_cache(None)
def dp(pos, prev_digit, is_tight, started):
if pos == len(digits): return 1 if started else 0
limit = int(digits[pos]) if is_tight else 9
result = 0
for d in range(0, limit + 1):
if started and d == prev_digit: continue # constraint: no repeat
result += dp(pos+1, d, is_tight and d==limit, started or d>0)
return result
return dp(0, -1, True, False)Interval DP Problem List
| Problem | Key Insight | LeetCode |
|---|---|---|
| Burst Balloons | Last balloon popped | 312 |
| Minimum Cost to Cut Stick | Cost = segment length | 1547 |
| Palindrome Partitioning II | Min cuts = min intervals | 132 |
| Longest Palindromic Subsequence | Expand/contract palindrome | 516 |
| Strange Printer | Last char printed | 664 |
| Zuma Game | Remove groups | 488 |
Interview Tips
- For interval DP: the outer loop must be on length, not on left boundary — always fill shorter intervals before longer ones
- Burst Balloons: the “last popped” framing is the key insight — it avoids tracking which balloons remain
- State machine DP: draw the state transitions explicitly before coding — hold/sold/rest or buy/sell/cooldown
- Tree DP: the function returns a tuple (include_root, exclude_root) — this is the pattern for House Robber III, maximum sum BST, etc.
- Digit DP: always use memoization with (position, prev_digit, is_tight, started) as state
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the interval DP pattern and how do you identify problems that use it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Interval DP solves optimization problems where the answer for interval [i,j] depends on answers for sub-intervals within it. Identification signals: (1) the input is a string or array and you need to find optimal ways to split, partition, or process it; (2) the order of operations matters (matrix chain multiplication, burst balloons); (3) the problem asks for min/max cost of some operation on the full array. Template: outer loop on interval length (2 to n), inner loops on left boundary and split point k. dp[i][j] = optimal(dp[i][k] + dp[k+1][j] + cost(i,k,j)) for all k. Key constraint: always iterate by length first so that sub-intervals are computed before the intervals that depend on them. Classic problems: Burst Balloons (LC 312), Minimum Cost to Cut Stick (LC 1547), Strange Printer (LC 664), Matrix Chain Multiplication.” }
},
{
“@type”: “Question”,
“name”: “What is the key insight for solving Burst Balloons with interval DP?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The naive approach asks "which balloon do I pop first?" – this splits the remaining balloons in complex ways. The key insight is to think backwards: "which balloon do I pop LAST in this interval?" If balloon k is the last one popped in interval (left, right), then when k is popped, all other balloons in (left, right) are already gone, so k is adjacent to the original boundary balloons nums[left] and nums[right]. Coins from popping k last = nums[left] * nums[k] * nums[right]. Before this, we independently maximize coins for (left, k) and (k, right). This framing makes sub-problems independent. dp[left][right] = max over all k in (left, right) of dp[left][k] + nums[left]*nums[k]*nums[right] + dp[k][right]. Add sentinel values 1 at both ends to handle boundaries cleanly.” }
},
{
“@type”: “Question”,
“name”: “How does state machine DP work for stock trading problems?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Model the problem as a finite state machine where the states represent different conditions (holding stock, just sold, resting). For Best Time to Buy and Sell Stock with Cooldown: three states: HOLD (own stock), SOLD (just sold today, cannot buy tomorrow), REST (available to buy). Transitions: HOLD -> SOLD (sell at current price), SOLD -> REST (mandatory cooldown), REST -> HOLD (buy at current price), REST -> REST (stay resting), HOLD -> HOLD (keep holding). At each time step, compute the max profit for each state: hold = max(prev_hold, prev_rest – price) [keep holding or buy], sold = prev_hold + price [sell], rest = max(prev_rest, prev_sold) [stay resting or come off cooldown]. This O(n) O(1)-space approach generalizes to any variation: with transaction fee, with K transactions, etc. Draw the state diagram before coding.” }
}
]
}