Dynamic Programming

01 / The shared mechanism

A table fills itself, one cell at a time — each entry composed from a constant number of earlier ones. The recurrence changes per sub-pattern, but the machinery — state, transition, fill order — is shared.

02 / The one-sentence essence

State is a range (i, j); the answer composes from smaller intervals inside [i, j]. Fill by increasing interval length, not by row — that's the only direction that guarantees the dependencies are ready.

Problemlongest palindromic substringInput"babad"n5

Each dp[i][j] answers: "is s[i..j] a palindrome?" Fill by interval length — 1 first, then 2, then 3, ...

step

0 / 12

interval len

—

best length

best range

[0, 0]

0 / 12

string

03 / The pattern signature

# interval DP — fill by length, not row# base cases: length 1 (and often length 2)for len in 2..n:for i in 0..n−len:j ← i + len − 1dp[i][j] ← f(dp[i+1][j−1], ...) or split over k in (i, j)return dp[0][n−1]# palindrome: dp[i][j] = (s[i]==s[j]) AND dp[i+1][j−1]# matrix chain: min over k in (i, j) of dp[i][k] + dp[k+1][j] + cost

04 / When to recognize this pattern

"range query"

The problem asks about a property of an arbitrary contiguous subarray or substring — palindrome, sorted, balanced. Sub-ranges are first-class.

"composes from inside out"

The answer for [i, j] depends only on intervals strictly inside — [i+1, j-1], or some [i, k] + [k+1, j]. The recursion peels from the outside.

"split point search"

Matrix chain, burst balloons, optimal BST — try every k in (i, j) and combine. The extra inner loop bumps complexity from O(N²) to O(N³).

"upper-triangular table"

Only cells with i ≤ j are meaningful — half the grid is unused. The fill order traces diagonals: main diagonal (length 1), then super-diagonal (length 2), then outward.

05 / Common pitfalls

Row-by-row fill instead of length-by-length.

If you iterate i outer and j inner, you'll try to read dp[i+1][j-1] before it's filled — that cell belongs to row i+1, which hasn't happened yet. The fix is to iterate length outer: every interval of length L is finished before any interval of length L+1 is touched.

ii.

Forgetting length-2 as a separate base case.

For palindromes, dp[i][i+1] = (s[i] == s[i+1]) can't fall out of the general recurrence because dp[i+1][i] is below the diagonal — an invalid interval, not false. Most clean implementations treat length 2 as a separate base case alongside length 1.

iii.

Choosing the wrong split granularity for "split point" interval DPs.

For matrix-chain or burst-balloons, the split k must range over the internal indices of (i, j) — and the meaning of k (left part is [i, k] vs [i, k-1]) is problem-specific. Off-by-one here corrupts everything.

06 / Go practice — on LeetCode

Four problems across the interval-DP family. The first two have direct inner-interval recurrences (length 2 jumps). The next two require a split-point search — every k in (i, j) is a candidate.

01Longest Palindromic Substring— LC 5medium→02Longest Palindromic Subseq— LC 516medium→03Burst Balloons— LC 312hard→04Minimum Cost Tree from Leaves— LC 1130medium→

— / When to use which

1-D linear

Use when the answer at index i depends on a constant number of earlier indices.

house-robber · climbing-stairs · max-subarray

2-D grid

Use when the state has two indices — a grid, or two interacting sequences.

min-path · LCS · edit-distance

knapsack

Use when each item triggers a choose-or-skip decision under a capacity constraint.

subset-sum · coin-change · partition

interval

Use when the state is a range (i, j) and the answer composes from inner intervals.

palindrome · matrix-chain · burst-balloons

state machine

Use when each index can be in one of several finite states with rules for transitioning between them.

stock · cooldown · two-state