Interval DP Introduction
Prerequisite: Dynamic Programming Introduction
Interval DP solves problems on subarrays or substrings where the answer for a range [l, r] depends on smaller ranges within it. The state dp[l][r] represents the answer for the subproblem covering indices l through r inclusive.
Identifying Interval DP Problems
Two signals indicate this pattern. First, the input is a linear sequence (array or string). Second, the problem requires considering all possible contiguous ranges, and solutions for larger ranges combine solutions from smaller ranges.
Common interval DP problems include optimal game strategies, palindrome partitioning, and merging stones. Constraints typically allow sequence lengths up to 500-1000, suggesting an O(n^2) or O(n^3) solution.
Example: Counting Palindromic Substrings
Given a string, count how many of its substrings are palindromes. A single character counts as a palindrome.
State: dp[l][r] = whether substring s[l..r] is a palindrome (true/false)
Transition: A substring is a palindrome if its outer characters match and the inner substring is also a palindrome:
dp[l][r] = (s[l] == s[r]) and dp[l+1][r-1]
Base case: l >= r → true (empty strings and single characters are palindromes)
Common Transition Patterns
Interval DP transitions typically examine smaller ranges within the current range. The two main patterns are element removal and interval splitting.
Element removal shrinks the range from one end. When checking whether a substring is a palindrome, removing the outer characters reduces [l, r] to [l+1, r-1].
Interval splitting divides the range at some point m. The state dp[l][r] tries all split points: dp[l][m] + dp[m+1][r] + cost(l, m, r). This requires iterating over all possible m values, adding an O(n) factor to each state.
Top-Down: The Natural Choice for Interval DP
Interval DP is one case where top-down is often easier than bottom-up. The reason: you don't need to figure out the processing order.
With bottom-up, you must ensure smaller intervals are computed before larger ones. This requires the non-obvious "iterate by length" pattern. With top-down, the recursion handles dependencies automatically—when solve(l, r) needs solve(l+1, r), it just calls the function, which computes and caches the result.
1from functools import lru_cache
2
3def count_palindromes(s):
4 n = len(s)
5
6 @lru_cache(maxsize=None)
7 def is_palin(l, r):
8 if l >= r:
9 return True
10 return s[l] == s[r] and is_palin(l + 1, r - 1)
11
12 return sum(is_palin(l, r) for l in range(n) for r in range(l, n))
The code reads exactly like the recurrence. No index manipulation, no worrying about which intervals to compute first.
Bottom-Up: Processing by Interval Length
If you prefer bottom-up or need to avoid recursion, you need to understand the state space and fill order.
The Two-Dimensional State Space
Unlike prefix-based DP where dp[i] considers elements 0..i, interval DP uses dp[l][r] to represent any contiguous range. For a sequence of length n, there are O(n^2) possible intervals, though only ranges where l <= r are valid (the upper triangle of the table).
Fill Order: By Increasing Length
Since larger intervals depend on smaller ones, process intervals in order of increasing length. Start with length 1 (base cases), then length 2, then length 3, up to length n. Within each length, iterate over all valid starting positions.
1def count_palindromes(s):
2 n = len(s)
3 dp = [[False] * n for _ in range(n)]
4
5 # Base case: single characters (length 1)
6 count = 0
7 for i in range(n):
8 dp[i][i] = True
9 count += 1
10
11 for length in range(2, n + 1): # substring length: 2, 3, ..., n
12 for l in range(n - length + 1): # l + length - 1 must be < n
13 r = l + length - 1 # right endpoint
14 dp[l][r] = s[l] == s[r] and (length == 2 or dp[l + 1][r - 1])
15 if dp[l][r]:
16 count += 1
17
18 return count
A brief note on indexing since it can get confusing: The outer loop picks a substring length. The inner loop picks the left endpoint l. Since the substring occupies length characters starting at l, the last character lands at index l + length - 1. This index must be at most n - 1, so l can go up to n - length. For example, in a string of length 6, substrings of length 4 can start at positions 0, 1, or 2 — that's 6 - 4 = 2.
This guarantees that when computing dp[l][r], the smaller interval dp[l+1][r-1] is already computed.
Time and Space Complexity
Interval DP uses O(n^2) space for the 2D table. Time complexity depends on the transition. Element removal (constant work per state) yields O(n^2) total. Interval splitting (trying all split points) yields O(n^3) total.