DP — interval, bitmask & tree
📖 Walk me through it — plain English
Dynamic programming (DP) just means: break a big problem into smaller versions of itself, solve each small one once, and write the answer in a table so you never redo it. This lesson is about three harder shapes of that idea. We'll focus on the first one in the code, interval DP, using its classic example: Matrix Chain Multiplication.
Here's the setup. When you multiply two matrices of sizes a×b and b×c, the cost (number of little multiplications) is a·b·c. If you have a chain of matrices to multiply, like A1·A2·A3, the final answer is the same no matter how you group the multiplications — but the cost changes a lot depending on grouping. So the question is: where do you put the parentheses to make the total cost smallest?
An everyday analogy: imagine stacking shipping boxes. You must combine them all into one stack, but each time you merge two sub-stacks it costs effort proportional to how big they are. The order you merge in changes the total effort, even though the final stack is identical. You want the cheapest merge order.
The plan: let dp[i][j] be the cheapest cost to multiply the chain from matrix i through matrix j. The last multiplication you do splits that range at some point k (you've already produced the left piece i..k and the right piece k+1..j, and now you combine those two). You try every split k and keep the cheapest. Because each piece is shorter than the whole, you must fill the table by increasing length — short ranges first — so the pieces already have answers when you need them.
Let's trace a tiny case. Dimensions are given as one list p = [10, 30, 5, 60], where matrix i has size p[i-1] × p[i]. That gives 3 matrices: A1 is 10×30, A2 is 30×5, A3 is 5×60. We fill dp by length.
Why it works: every grouping has some last combine step, and that step splits the chain into a left half and a right half. By trying all possible split points and trusting that the halves were already solved cheapest (because we filled shorter lengths first), we're guaranteed to find the overall cheapest. The cost is O(n³): there are about n² ranges to fill, and each range tries up to n split points. The two other families in this lesson reuse the same "define a state, recurse, cache" recipe — bitmask DP packs a set of used items into the bits of an integer, and tree DP lets each node combine answers returned from its children — but interval DP is the cleanest place to see the pattern.
Once linear and grid DP feel routine, three harder shapes account for almost everything else. The unifying idea is unchanged — define a state, recurse into smaller subproblems, cache — but the geometry of "smaller" changes. In interval DP, dp[i][j] covers a contiguous range and you split it at some point k strictly inside (i, j); the anchor problem is Matrix Chain Multiplication, where the last multiply you perform partitions the chain into two already-solved halves. In bitmask DP the state carries a set of "used" items as the bits of an integer — dp[mask][i] for the Travelling Salesman problem means "cheapest route that has visited exactly the cities in mask and is now sitting at city i." In tree DP, a single post-order DFS lets each node combine answers returned from its children; House Robber III and Binary Tree Maximum Path Sum are the canonical pair. The recurring trap is ordering and bookkeeping: interval DP must fill by increasing length so the halves exist before the whole, and tree DP must separate what it returns to the parent from the global best.
- "Best way to combine / partition a contiguous range" — parenthesize, burst, cut. Reach for dp[i][j] + a split.
- Optimal order of operations on a sequence (multiplication, merging stones, removing boxes).
- A set of items must each be used once and n ≤ ~20 — visited-set fits in an int. TSP, job assignment, "shortest superstring".
- Input is a tree and the answer at a node depends on subtree answers — rob/skip, path sums, diameter, subtree counts.
- "Count numbers in [L, R] with property P" — digit DP over positions with a tight flag.
- Interval. dp[i][j], split on k. Matrix Chain · Burst Balloons · Palindrome Partitioning II. O(n³) time, O(n²) space.
- Bitmask. dp[mask][i]. TSP · assignment problem. O(2ⁿ·n²) time, O(2ⁿ·n) space.
- Tree. post-order DFS returns to parent. House Robber III · Max Path Sum · diameter. O(n) time, O(h) stack.
- Digit (aside). recurse over digit positions carrying (index, tight, …) to count constrained integers.
# p has n+1 dims; matrix i is p[i-1] x p[i], for i in 1..n
def matrix_chain(p):
n = len(p) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)] # dp[i][j], 1-indexed
for L in range(2, n + 1): # L = chain length, ASCENDING
for i in range(1, n - L + 2): # left endpoint
j = i + L - 1 # right endpoint
dp[i][j] = float('inf')
for k in range(i, j): # split: i..k | k+1..j (k strictly < j)
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
if cost < dp[i][j]:
dp[i][j] = cost
return dp[1][n] # whole chain 1..n
# --- tree DP: post-order, return-to-parent vs global best ---
# Binary Tree Maximum Path Sum
def max_path_sum(root):
best = float('-inf')
def gain(node): # best downward path STARTING at node
nonlocal best
if not node: return 0
l = max(gain(node.left), 0) # drop negative branches
r = max(gain(node.right), 0)
best = max(best, node.val + l + r) # path THROUGH node (two sides) -> global
return node.val + max(l, r) # extend ONE side -> what parent can use
gain(root)
return best// interval DP — Matrix Chain; p[i-1] x p[i] is matrix i
function matrixChain(p: number[]): number {
const n = p.length - 1;
const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
for (let L = 2; L <= n; L++) { // length ascending
for (let i = 1; i + L - 1 <= n; i++) {
const j = i + L - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) { // split point in (i, j)
const cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if (cost < dp[i][j]) dp[i][j] = cost;
}
}
}
return dp[1][n];
}
// tree DP — Binary Tree Maximum Path Sum
function maxPathSum(root: TreeNode | null): number {
let best = -Infinity;
const gain = (node: TreeNode | null): number => {
if (!node) return 0;
const l = Math.max(gain(node.left), 0); // drop negative branches
const r = Math.max(gain(node.right), 0);
best = Math.max(best, node.val + l + r); // two-sided path THROUGH node -> global
return node.val + Math.max(l, r); // one side -> what parent can extend
};
gain(root);
return best;
}- Interval order is non-negotiable. Loop on length ascending, not on i/j directly — when you compute dp[i][j] the halves dp[i][k] and dp[k+1][j] are strictly shorter, so they must already be filled. Sweeping i ascending then j ascending reads cells that are still garbage.
- Split is strictly interior. k ranges over (i, j); if a side can be empty, handle that base case explicitly. Length-1 intervals (single matrix / single char) are the 0 base.
- Interval DP is O(n³): O(n²) states × O(n) splits, with O(n²) space. Palindrome Partitioning II drops time to O(n²) by precomputing an isPalin[i][j] table, then a 1D cut DP.
- Bitmask blows up fast. 2ⁿ states means n=20 is ~1M masks (fine), n=25 is ~33M, and a mask for n=32 needs all 32 bits — past a signed 32-bit int. Past ~20 it is usually not a bitmask problem — look for greedy, branch-and-bound, or a different state.
- Tree DP: return value ≠ answer. Max Path Sum returns a one-sided path (parent can only extend down one branch) but updates the global best with the two-sided path through the node. Conflating them is the classic bug.
- Tree DP is one pass, O(n), but watch recursion depth on a skewed tree (~n stack frames). Digit DP memoizes on (pos, tight, …); the tight flag must be part of the key (or the tight branch left uncached), or counts leak across the bound.
Binary tree maximum path sum — tree DP with a global best: