Interval and Tree DP
What is this?
All three problems answer a question about a range by choosing something inside it and recursing on what remains. Choose the two ends of a palindrome and look between them. Choose which operator is applied last and recurse on both sides. Choose the root and multiply the counts of the two subtrees.
The pattern is the same each time; what differs is what the choice is, and whether the halves combine by addition, multiplication, or something that needs care about double counting.
Fun fact: Unique Binary Search Trees produces the Catalan numbers (1, 1, 2, 5, 14, 42, 132), and so do several other counts: the ways to parenthesise a product, the ways to triangulate a convex polygon, the balanced bracket strings with n pairs, and the lattice paths that never cross a diagonal. They share the recurrence
G(n) = Σ G(i) · G(n−1−i), because each is "pick a split point, multiply the two sides". Once you recognise the shape, the other counts are the same derivation.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: fix a split point inside the range, solve both sides, and combine. The combination rule is the problem: sum, product, or a correction for what you counted twice.
1. Combine by product
G = [0] * (n + 1); G[0] = 1
for i in range(1, n + 1):
for r in range(i): # r nodes on the left, i-1-r on the right
G[i] += G[r] * G[i - 1 - r]
return G[n]
Only the shape matters, not the values: any i distinct sorted values give the same count of BST shapes, which is why one array indexed by size suffices instead of a table indexed by range. That reduction from O(n²) states to O(n) is worth stating explicitly: it is the whole reason this is a one-dimensional loop.
Different Ways to Add Parentheses is the same shape without the reduction. Splitting at each operator, the left side yields a list of values and the right side another, and the combination is every pairing:
for a in left:
for b in right:
out.append(apply(op, a, b))
Memoising on the substring matters here: the same sub-expression is reached through many different split orders. With k numbers there are only O(k²) distinct spans, so each is solved once. The total work is still proportional to the pairs combined, and the output itself is Catalan-sized, so memoisation removes recomputation but cannot shrink the answer.
2. Combine with a correction
Count Different Palindromic Subsequences is the hard one, because subsequences (unlike substrings) can be reached many ways and must be counted once.
if s[i] != s[j]:
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] # inclusion–exclusion
else:
lo, hi = first and last index strictly inside equal to s[i] # scan, or O(1) lookup
if lo > hi: dp[i][j] = 2 * dp[i+1][j-1] + 2 # no repeat inside: add "a" and "aa"
elif lo == hi: dp[i][j] = 2 * dp[i+1][j-1] + 1 # one repeat: "aa" already counted
else: dp[i][j] = 2 * dp[i+1][j-1] - dp[lo+1][hi-1] # subtract the double count
When the ends differ, the middle term is subtracted because it was counted in both of the first two. When the ends match, every palindrome strictly inside can be wrapped by the matching pair (hence the 2 ×) and the correction depends on whether that same character already appears inside. Finding lo and hi by scanning costs up to O(n) per cell, so the plain version is O(n³), not O(n²). The alphabet is only a to d, which lets you precompute, for every position and letter, the next and previous occurrence. Those lookups make lo and hi O(1) and the whole DP a true O(n²). For example, "abba" gives 6 and "abcdabcdabcdabcd" gives 244.
Everything is taken modulo 10⁹ + 7, including the subtractions, which can go negative before the modulo is applied.
3. A 30-second worked example (Catalan)
n = 3: count the BST shapes over three sorted values.
The values never appear in the arithmetic, only the counts on each side. That is what collapses a range-indexed table into a single array indexed by size, and the same collapse is available whenever the answer depends on the size of a range rather than on its contents.
4. Where you'll actually meet this
- Compilers and calculators. Every parse of an ambiguous expression is exactly the parenthesisation problem.
- Query planners. Join ordering is "split, solve both sides, combine", with cost instead of count.
- Computational biology. RNA secondary-structure prediction is an interval DP over paired bases.
- Sizing a search space. Catalan numbers count bracket nestings and binary tree shapes, which tells you how many candidates an enumerator will produce.
5. Problems in this chapter
Count Different Palindromic Subsequences
Count distinct palindromic subsequences modulo 10⁹+7. Interval DP with inclusion-exclusion and a correction for repeated boundary characters.
Pattern: interval DP + distinctness correction. Target: O(n²) time and space using next/previous occurrence tables; scanning for the inner matches is O(n³).
Different Ways to Add Parentheses
Every value the expression can take. Split at each operator, recurse on both sides, and combine every left value with every right.
Pattern: divide and conquer with memoisation. Target: O(k²) distinct spans over k numbers, with total work bound by the Catalan-sized output.
Unique Binary Search Trees
Count BST shapes over n values. Fix each value as the root and multiply the counts of the two sides.
Pattern: the Catalan recurrence. Target: O(n²) time, O(n) space. C₁₉ = 1,767,263,190 fits in a signed 32-bit int, C₂₀ does not; a signed 64-bit int holds up to C₃₅.
6. Common pitfalls
- Counting duplicate subsequences. Distinctness is the entire difficulty; a plain palindrome count is a different problem.
- Skipping the inclusion–exclusion subtraction when the ends differ, which double counts the middle.
- Taking a modulo without normalising a negative. The subtraction can go below zero first.
- Indexing BST counts by range rather than by size, which is a needless dimension.
- Not memoising the parenthesisation split, so the same sub-expression is recomputed many times.
- Filling an interval DP in the wrong order. Shorter ranges must be complete before longer ones: loop over length.
- Forgetting the base cases.
dp[i][i] = 1andG[0] = 1are what everything else is built from.
7. Key takeaways
- Fix something inside the range and recurse: the ends, the last operator, the root.
- The combination rule is the problem. Sum, product, or a correction for double counting.
- Inclusion–exclusion is how distinctness is enforced when subsequences overlap.
- If only the size matters, index by size. That is a whole dimension saved.
- Loop by interval length, so every sub-range is final before it is read.
- Catalan numbers announce themselves as "split and multiply", so learn the shape once.
- Derive, don't recite. Explaining why the recurrence holds matters more than remembering it.
Order: Count Different Palindromic Subsequences → Different Ways to Add Parentheses → Unique Binary Search Trees.