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.

flowchart TD A["answer for a range [i..j]"] --> B["fix something inside it"] B --> C["the two ends
→ Count Palindromic Subsequences"] B --> D["the last operator applied
→ Different Ways to Add Parentheses"] B --> E["the root
→ Unique Binary Search Trees"] C --> C1["ends equal? inclusion–exclusion
on the repeats inside"] D --> D1["combine: every left × every right"] E --> E1["combine: count(left) × count(right)"]

💡 Fun fact: Unique Binary Search Trees produces the Catalan numbers — 1, 1, 2, 5, 14, 42, 132 — and so do a startling number of other things: the ways to parenthesise a product, the ways to triangulate a polygon, the number of balanced bracket strings of a given length, and the paths that never cross a diagonal. They all reduce to the same recurrence, G(n) = Σ G(i) · G(n−1−i), because they are all "pick a split point, multiply the two sides". Recognising the shape means you have already solved the next four problems that wear it.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line 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.

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]
    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. The alphabet is only a–d, which is the hint that the inner scan is affordable.

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.

root = 1st value:   left has 0 nodes, right has 2   →  G(0) · G(2) = 1 · 2 = 2
root = 2nd value:   left has 1 node,  right has 1   →  G(1) · G(1) = 1 · 1 = 1
root = 3rd value:   left has 2 nodes, right has 0   →  G(2) · G(0) = 2 · 1 = 2

G(3) = 2 + 1 + 2 = 5

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.
Text and DNA analysis. Counting distinct palindromic subsequences appears in sequence-similarity work.
Combinatorics in production. Catalan numbers count valid nestings — brackets, transactions, tree shapes.

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.

▶ 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: Catalan-many results — output-bound.

▶ 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.

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] = 1 and G[0] = 1 are 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" — learn the shape once.
Why interviewers like it: the recurrence cannot be recalled from memory, so deriving it in front of them is real evidence.

Order: Count Different Palindromic Subsequences → Different Ways to Add Parentheses → Unique Binary Search Trees.

Advanced