Interval DP Introduction
Prerequisite: Dynamic Programming Introduction
Interval DP solves problems on contiguous ranges in an array or string. Instead of asking "what is the answer up to index i?", you ask "what is the answer on range [l, r]?". The state dp[l][r] stores the answer for the subproblem that uses only indices l through r.
Identifying Interval DP Problems
This pattern usually appears when the input is a linear sequence and the problem asks you to reason about many substrings or subarrays. A larger range depends on smaller ranges inside it, so previously solved intervals can be reused.
Common examples are palindromes, game strategies on arrays, and merge-cost problems. The constraint on n is often in the few hundreds, which is a strong hint that O(n^2) or O(n^3) DP is expected.
Example: Counting Palindromic Substrings
Given a string, count how many of its substrings are palindromes. A single character counts as a palindrome.
Let dp[l][r] be whether substring s[l..r] is a palindrome.
The transition follows the palindrome definition. A substring is a palindrome when the outer characters match and the inner substring is also a palindrome:
dp[l][r] = (s[l] == s[r]) and dp[l+1][r-1]
The base case is l >= r, which means the substring has length 0 or 1 and is always a palindrome.
Common Transition Patterns
Most interval DP recurrences follow one of two shapes.
The first shape is element removal, where you shrink the interval. In palindrome checking, you compare s[l] and s[r], then recurse on the inner interval [l+1, r-1].
The second shape is interval splitting. You choose a split point m, combine answers from [l, m] and [m+1, r], and possibly add a merge cost:
dp[l][r] = best over m of (dp[l][m] + dp[m+1][r] + cost(l, m, r))
Because each state tries many split points, this version often costs O(n^3) in total.
Top-Down: The Natural Choice for Interval DP
Interval DP is one case where top-down is often easier than bottom-up because you do not need to design a fill order first.
With bottom-up, larger intervals must wait until smaller intervals are ready, so you need the "iterate by length" technique. With top-down memoization, recursion already follows dependencies. If solve(l, r) needs solve(l+1, r-1), it calls it directly 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))
This code mirrors the recurrence directly, which is why top-down is a common first implementation.
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
Prefix-style DP uses one index (dp[i]) and usually grows left to right. Interval DP uses two indices (dp[l][r]) to represent every contiguous range. For length n, there are O(n^2) valid intervals with l <= r, which form the upper triangle of the DP table.
Fill Order: By Increasing Length
Since long intervals depend on shorter intervals, fill by increasing interval length. Start at length 1, then 2, then 3, up to n. For each fixed length, sweep all valid left endpoints.
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
Indexing is easier if you derive it once. The outer loop chooses length. The inner loop chooses l. Then r = l + length - 1. Since r must be at most n - 1, the largest valid l is n - length. For example, if n = 6 and length = 4, valid starts are l = 0, 1, 2.
This order guarantees that when you compute dp[l][r], its dependency dp[l+1][r-1] is already available.
Time and Space Complexity
Interval DP usually uses O(n^2) space for the 2D table. The time depends on the recurrence. If each state does constant work (like checking outer characters), total time is O(n^2). If each state tries all split points, total time becomes O(n^3).