Appearance
4.22.1 — Four DP Shapes Worked by Hand: Knapsack, Intervals, Subsets and Trees
You are packing a cabin bag with a 5 kg limit. On the bed are a camera (1 kg, and you would pay ₹6,000 not to leave it behind), a laptop (2 kg, ₹10,000) and noise-cancelling headphones (3 kg, ₹12,000). Everything together weighs 6 kg, so something stays home. Which combination is worth the most?
Greedy picks the most valuable item per kilogram first: the camera at ₹6,000 per kg, then the laptop at ₹5,000 per kg. That is 3 kg and ₹16,000, and the headphones no longer fit. The real answer is laptop plus headphones, exactly 5 kg and ₹22,000. Greedy lost ₹6,000 because taking the camera early quietly used up the space the better pair needed. A choice now restricted the choices later, which is the first tell of dynamic programming from 4.22.
That chapter named the classical shapes of DP and gave four of them only a sentence each. This page works each of those four by hand, with real numbers in a table, because a shape you have traced once is a shape you recognise in an interview.
1. Knapsack: a table you can fill with a pencil
The state. dp[i][c] is the most value you can carry using only the first i items with a bag that holds c kilograms. Say it as a sentence before writing code; that sentence is the whole design.
The choice. For item i there are two options. Leave it, and the answer is whatever the first i − 1 items could do with the same space: dp[i−1][c]. Or take it, if it fits, and the answer is its value plus the best the first i − 1 items could do with the space that is left: dp[i−1][c − w] + v. Keep the larger.
python
def best_bag(weights: list[int], values: list[int], capacity: int) -> int:
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)] # (1)
for i in range(1, n + 1): # (2)
w, v = weights[i - 1], values[i - 1]
for c in range(capacity + 1):
dp[i][c] = dp[i - 1][c] # (3) skip item i
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v) # (4) take item i
return dp[n][capacity]
print(best_bag([1, 2, 3], [6, 10, 12], 5)) # → 22 (values in thousands of rupees)ts
function bestBag(weights: number[], values: number[], capacity: number): number {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => new Array<number>(capacity + 1).fill(0)); // (1)
for (let i = 1; i <= n; i++) { // (2)
const w = weights[i - 1], v = values[i - 1];
for (let c = 0; c <= capacity; c++) {
dp[i][c] = dp[i - 1][c]; // (3) skip item i
if (w <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + v); // (4) take item i
}
}
return dp[n][capacity];
}
console.log(bestBag([1, 2, 3], [6, 10, 12], 5)); // → 22- One extra row and one extra column. Row 0 means "no items yet" and column 0 means "a bag that holds nothing". Both are 0, and they are the base cases, so the code never needs a special
iffor them. - Rows are filled top to bottom, because row
ionly ever reads rowi − 1. That is the fill-order question from 4.22, answered by looking at what the recurrence reads. - Skipping item
icosts nothing and changes nothing: copy the value from directly above. - Taking item
ireads the row above,wcolumns to the left. Reading the row above is what guarantees each item is used at most once: the value atdp[i−1][c−w]was computed before itemiexisted.
Here is the finished table. Rows are items added one at a time, columns are bag sizes 0 to 5 kg, values are in thousands of rupees.
| After adding | 0 kg | 1 kg | 2 kg | 3 kg | 4 kg | 5 kg |
|---|---|---|---|---|---|---|
| nothing | 0 | 0 | 0 | 0 | 0 | 0 |
| camera (1 kg, 6) | 0 | 6 | 6 | 6 | 6 | 6 |
| laptop (2 kg, 10) | 0 | 6 | 10 | 16 | 16 | 16 |
| headphones (3 kg, 12) | 0 | 6 | 10 | 16 | 18 | 22 |
Check one cell the way you would on a whiteboard. The bottom-right cell asks: headphones row, 5 kg. Skip the headphones and you get the cell above, 16. Take them (3 kg, 12) and you get 12 plus the laptop row at 5 − 3 = 2 kg, which is 10, total 22. The larger is 22. Every other cell is the same two-line check.
Recovering which items, not just the value. Walk back from the answer cell. The value 22 differs from the cell above it (16), so the headphones were taken; move up a row and left 3 columns to the laptop row at 2 kg. The value 10 differs from the cell above (6), so the laptop was taken; move up and left 2 columns to the camera row at 0 kg, where the value is 0 and you stop. Laptop and headphones, as promised.
Rolling it to one row, and the loop direction that changes the problem
Row i reads only row i − 1, so 4.22's space trick applies: keep one array and overwrite it. Now the direction of the inner loop decides whether each item is used once or as often as you like. Watch it happen with just the camera (1 kg, 6) and a 5 kg bag.
Downwards, from 5 kg to 1 kg. At 5 kg the code reads dp[4], which still holds the old value 0, so dp[5] becomes 6. At 4 kg it reads dp[3], also still 0, and so on. Every cell ends at 6: one camera.
Upwards, from 1 kg to 5 kg. At 1 kg, dp[1] becomes 0 + 6 = 6. At 2 kg it reads dp[1], which already contains this camera, and becomes 12. At 3 kg it becomes 18, and at 5 kg it reaches 30: five cameras.
| Bag size | 1 kg | 2 kg | 3 kg | 4 kg | 5 kg |
|---|---|---|---|---|---|
| Downwards loop | 6 | 6 | 6 | 6 | 6 |
| Upwards loop | 6 | 12 | 18 | 24 | 30 |
So the same one-line loop is 0/1 knapsack when it runs downwards and unbounded knapsack (unlimited copies of each item) when it runs upwards. Coin Change, where each coin can be used again, is the upward version (4.23.8); Partition Equal Subset Sum, where each number is used once, is the downward one (4.23.12).
Complexity, derived. There are (n+1) \times (C+1) cells and each does constant work, so O(nC) time; the rolled version uses O(C) space. Notice that C is a number in the input, not the length of the input. A capacity of a billion makes the table a billion columns wide. That is why knapsack is called "pseudo-polynomial": fast when the capacity is small, hopeless when it is huge. In the general case nobody knows a truly polynomial algorithm, because 0/1 knapsack is NP-hard (4.29).
2. Interval DP: cutting a stick in the cheapest order
A carpenter has a 7-metre beam and must cut it at the 1, 3, 4 and 5 metre marks. The saw charges by the length of the piece being cut, so cutting the full 7 m beam costs 7, and cutting a 2 m offcut costs 2. The cuts can be made in any order. What order is cheapest?
The insight is in the figure. Whatever cut you make first costs the full length of the current piece and splits it into a left piece and a right piece. Those two pieces never interact again: cuts on the left beam cannot change the cost of cuts on the right. So the cheapest plan for a piece is "try every first cut, and for each one add the cheapest plan for its left piece and its right piece".
The state. Put the beam's ends and the cut marks in one sorted list: points = [0, 1, 3, 4, 5, 7]. Then dp[i][j] is the cheapest way to make every cut strictly between points[i] and points[j]. The answer is dp[0][5], the whole beam.
python
def min_cut_cost(length: int, cuts: list[int]) -> int:
points = [0] + sorted(cuts) + [length] # (1)
m = len(points)
dp = [[0] * m for _ in range(m)] # (2)
for gap in range(2, m): # (3)
for i in range(m - gap):
j = i + gap
dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) \
+ (points[j] - points[i]) # (4)
return dp[0][m - 1]
print(min_cut_cost(7, [1, 3, 4, 5])) # → 16ts
function minCutCost(length: number, cuts: number[]): number {
const points = [0, ...[...cuts].sort((a, b) => a - b), length]; // (1)
const m = points.length;
const dp = Array.from({ length: m }, () => new Array<number>(m).fill(0)); // (2)
for (let gap = 2; gap < m; gap++) { // (3)
for (let i = 0; i + gap < m; i++) {
const j = i + gap;
let best = Infinity;
for (let k = i + 1; k < j; k++) best = Math.min(best, dp[i][k] + dp[k][j]);
dp[i][j] = best + (points[j] - points[i]); // (4)
}
}
return dp[0][m - 1];
}
console.log(minCutCost(7, [1, 3, 4, 5])); // → 16- The beam's two ends join the cut marks, so every piece of beam is "from one point in this list to another". Sorting matters: the TypeScript copies the array before sorting, because
sortchanges the array in place and the caller's list should not change. dp[i][i+1]stays 0: a piece between two neighbouring points has no cuts left to make. These are the base cases.- The fill order is by piece length, not by row. A piece spanning
gappoints depends only on shorter pieces inside it, so fill all pieces of gap 2, then gap 3, and so on up to the whole beam. Filling row by row would read cells that are not ready yet. This "shortest intervals first" order is the signature of interval DP. - Try every cut mark
kinside the piece as the first cut, add the two sub-pieces, keep the cheapest, then add the cost of this first cut, which is the piece's length.
The filled table. Only the upper half means anything (i is the left point, j the right), and a blank cell is a piece with no cut mark inside it, which costs 0:
dp[i][j] | j=2 (3 m) | j=3 (4 m) | j=4 (5 m) | j=5 (7 m) |
|---|---|---|---|---|
| i=0 (0 m) | 3 | 7 | 10 | 16 |
| i=1 (1 m) | 3 | 6 | 12 | |
| i=2 (3 m) | 2 | 6 | ||
| i=3 (4 m) | 3 |
Check the answer cell. For the whole beam, try each first cut. Cutting at 1 m costs 7 + dp[0][1] (0) + dp[1][5] (12) = 19. At 3 m: 7 + dp[0][2] (3) + dp[2][5] (6) = 16. At 4 m: 7 + 7 + 3 = 17. At 5 m: 7 + 10 + 0 = 17, because the piece from 5 to 7 m has no cuts left. The cheapest is 16, cutting at 3 m first. Cutting left to right in the obvious order would cost 7 + 6 + 4 + 3 = 20.
Complexity, derived. With m points there are about m^2/2 pieces, and each piece tries up to m first cuts, so O(m^3) time and O(m^2) space. That cube is the reason interval DP problems come with small limits, typically up to a few hundred points. Burst Balloons (4.24.10) is this exact shape with one twist: there you choose the last balloon to burst in a range rather than the first cut, because the last one is the one whose neighbours are known.
3. Bitmask DP: the shortest delivery round
A delivery van leaves the depot, visits three shops once each, and returns. Trying every order works for three shops (3! = 6 orders) and dies quickly: 15 shops have 1.3 trillion orders. Bitmask DP gets the exact answer much faster by noticing that the past matters less than it seems.
The insight. Suppose the van has visited shops 1 and 2, in some order, and is now at shop 2. For the rest of the route, does it matter whether it went 1 → 2 or came straight to 2 first? No. The only things that affect the future are which shops are already done and where the van is now. So we only need the cheapest way to reach each such situation, not every route.
The set as a number. "Which shops are done" is a set, and a set of up to about 20 items fits in the bits of one integer: bit k is 1 if place k has been visited (4.30.0). With the depot as place 0 and shops 1, 2, 3, the mask 0b0111 means "depot, shop 1 and shop 2 are done". Checking membership is mask & (1 << k), and adding a place is mask | (1 << k).
The state. dp[mask][last] is the shortest distance that starts at the depot, visits exactly the places in mask, and ends at last.
The distances, in kilometres:
| from \ to | depot | shop 1 | shop 2 | shop 3 |
|---|---|---|---|---|
| depot | 0 | 4 | 9 | 7 |
| shop 1 | 4 | 0 | 3 | 8 |
| shop 2 | 9 | 3 | 0 | 2 |
| shop 3 | 7 | 8 | 2 | 0 |
python
def shortest_round(dist: list[list[int]]) -> int:
n = len(dist)
INF = float("inf")
dp = [[INF] * n for _ in range(1 << n)] # (1)
dp[1][0] = 0 # (2)
for mask in range(1 << n):
for last in range(n):
if dp[mask][last] == INF:
continue
for nxt in range(n):
if mask & (1 << nxt): # (3)
continue
new_mask = mask | (1 << nxt)
dp[new_mask][nxt] = min(dp[new_mask][nxt],
dp[mask][last] + dist[last][nxt]) # (4)
full = (1 << n) - 1
return min(dp[full][last] + dist[last][0] for last in range(1, n)) # (5)
D = [[0, 4, 9, 7], [4, 0, 3, 8], [9, 3, 0, 2], [7, 8, 2, 0]]
print(shortest_round(D)) # → 16ts
function shortestRound(dist: number[][]): number {
const n = dist.length;
const dp = Array.from({ length: 1 << n }, () => new Array<number>(n).fill(Infinity)); // (1)
dp[1][0] = 0; // (2)
for (let mask = 0; mask < 1 << n; mask++) {
for (let last = 0; last < n; last++) {
if (dp[mask][last] === Infinity) continue;
for (let next = 0; next < n; next++) {
if (mask & (1 << next)) continue; // (3)
const newMask = mask | (1 << next);
dp[newMask][next] = Math.min(dp[newMask][next], dp[mask][last] + dist[last][next]); // (4)
}
}
}
const full = (1 << n) - 1;
let best = Infinity;
for (let last = 1; last < n; last++) best = Math.min(best, dp[full][last] + dist[last][0]); // (5)
return best;
}
console.log(shortestRound([[0, 4, 9, 7], [4, 0, 3, 8], [9, 3, 0, 2], [7, 8, 2, 0]])); // → 16- One row per possible set of visited places (2^n of them) and one column per place the van could be standing. Everything starts as "unreachable".
- The only starting situation: just the depot visited (mask
0b0001), standing at the depot, distance 0. - Skip places already in the set, because each shop is visited once.
- Extend the route by one place. A bigger mask is always a bigger number than the mask it came from, so looping masks in increasing order guarantees every situation is final before anything extends it. That is the fill order, and it falls out of how binary numbers work.
- Once every place is in the mask, add the drive back to the depot and take the best finishing shop.
Here is every reachable situation the loop fills in, in kilometres:
| Visited (mask) | at depot | at shop 1 | at shop 2 | at shop 3 |
|---|---|---|---|---|
depot (0001) | 0 | |||
+ shop 1 (0011) | 4 | |||
+ shop 2 (0101) | 9 | |||
+ shops 1, 2 (0111) | 12 | 7 | ||
+ shop 3 (1001) | 7 | |||
+ shops 1, 3 (1011) | 15 | 12 | ||
+ shops 2, 3 (1101) | 9 | 11 | ||
all (1111) | 12 | 14 | 9 |
Read the last row and add the drive home: ending at shop 1 is 12 + 4 = 16, at shop 2 is 14 + 9 = 23, at shop 3 is 9 + 7 = 16. The answer is 16, the route depot → shop 3 → shop 2 → shop 1 → depot (7 + 2 + 3 + 4), or the same loop driven the other way. Checking all six orders by hand gives the same 16.
Complexity, derived. There are 2^n \times n states and each tries n next places, so O(2^n n^2) time and O(2^n n) space. For 15 places that is about 7.4 million steps instead of 1.3 trillion orders. It is still exponential, so the trick runs out around n = 20, where 2^{20} \times 400 is about 420 million steps. The tell in a problem statement is a suspiciously small limit such as "at most 16 workers" or "up to 20 cities": the setter is telling you the set fits in an integer.
4. Tree DP: robbing houses arranged as a tree
Houses on a street are a line, and 4.22's House Robber walks along it with two rolling numbers. Now the houses form a tree: each house connects to at most two houses below it, and the rule is that you cannot rob two houses joined by a direct link. This is LeetCode 337, House Robber III, and the trick is to ask each house for two answers instead of one.
Why one number per house is not enough. If a child only reports "the best I can do", the parent cannot tell whether that best already robbed the child, and the parent is forbidden from being robbed together with it. So each house reports a pair: the best total in its subtree if this house is robbed, and the best if it is skipped. With both numbers the parent can follow the rule.
python
from typing import Optional
class TreeNode:
def __init__(self, val: int, left: "Optional[TreeNode]" = None,
right: "Optional[TreeNode]" = None):
self.val, self.left, self.right = val, left, right
def rob_tree(root: Optional[TreeNode]) -> int:
def visit(node: Optional[TreeNode]) -> tuple[int, int]: # (1)
if node is None:
return (0, 0)
l_take, l_skip = visit(node.left) # (2)
r_take, r_skip = visit(node.right)
take = node.val + l_skip + r_skip # (3)
skip = max(l_take, l_skip) + max(r_take, r_skip) # (4)
return (take, skip)
return max(visit(root))
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # → 7ts
interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }
function robTree(root: TreeNode | null): number {
const visit = (node: TreeNode | null): [number, number] => { // (1)
if (node === null) return [0, 0];
const [lTake, lSkip] = visit(node.left); // (2)
const [rTake, rSkip] = visit(node.right);
const take = node.val + lSkip + rSkip; // (3)
const skip = Math.max(lTake, lSkip) + Math.max(rTake, rSkip); // (4)
return [take, skip];
};
return Math.max(...visit(root));
}
const leaf = (val: number): TreeNode => ({ val, left: null, right: null });
console.log(robTree({ val: 3, left: { val: 2, left: null, right: leaf(3) },
right: { val: 3, left: null, right: leaf(1) } })); // → 7- Every house returns its pair. A missing child returns (0, 0): nothing to rob, nothing lost.
- Children first, then the parent. This is the post-order traversal from 4.14.0: a house can only decide after both children have reported, so the recursion naturally fills the "table" from the leaves upward. There is no array at all; the state lives in the return values.
- Robbing this house forbids robbing either child, so add the children's skip numbers.
- Skipping this house leaves each child free to do whatever is best for it, robbed or not.
The pairs, filled from the bottom of the tree to the top:
| House | Robbed | Skipped | How |
|---|---|---|---|
| ₹3 (bottom left) | 3 | 0 | a leaf: its own value, or nothing |
| ₹1 (bottom right) | 1 | 0 | a leaf |
| ₹2 (middle left) | 2 | 3 | robbed: 2 + 0; skipped: best of its child (3, 0) = 3 |
| ₹3 (middle right) | 3 | 1 | robbed: 3 + 0; skipped: best of (1, 0) = 1 |
| ₹3 (top) | 7 | 6 | robbed: 3 + 3 + 1; skipped: 3 + 3 |
The top house's robbed total is 7, from the top house and the two bottom houses, none of which are directly linked.
Complexity, derived. Each house is visited once and does constant work, so O(n) time; the recursion is as deep as the tree is tall, so O(h) extra space, which is O(n) for a tree shaped like a chain. If you have already solved Diameter of a Binary Tree (4.14.3) or Binary Tree Maximum Path Sum (4.14.14), you have already written tree DP: each of those returns one number upward while tracking a second answer on the side. The shape is always the same: decide what a parent needs to know from each child, return exactly that, and combine in post-order.
5. The four shapes side by side
| Shape | State | Fill order | Cost |
|---|---|---|---|
| Knapsack | item, capacity | item by item | O(nC) |
| Interval | left end, right end | shortest first | O(n^3) |
| Bitmask | set, current place | masks ascending | O(2^n n^2) |
| Tree | one node, returning a pair | children first | O(n) |
The table is the one idea of DP repeated four times. Each shape answers "what is the smallest set of facts that decides the rest of the problem?" differently: remaining space, the piece still to cut, the places still to visit, what the parent needs from its children. Find that set of facts and the code is the same two moves every time, try each choice and keep the best.
What the interviewer will push on
"Why does 0/1 knapsack loop the capacity downwards in the one-row version?" They are checking that you understand why, not that you remember the rule. The strong answer traces it: going upwards, the cell you read has already been updated with the current item, so the item is used twice. Then name the consequence, that the upward loop is the unbounded problem, and show the camera table (6 everywhere versus 6, 12, 18, 24, 30). A memorised answer stops at "otherwise it is wrong".
"Is knapsack polynomial?" The trap is saying yes because O(nC) looks polynomial. It is polynomial in the value of C, not in the number of digits needed to write C, so doubling the length of the input can square the work. The word to use is pseudo-polynomial, and the follow-up is that 0/1 knapsack is NP-hard in general.
"How do you know the fill order in interval DP?" By what a cell reads: a piece reads only strictly shorter pieces inside it, so you fill by increasing length. The common wrong answer is a plain row-by-row loop, which reads cells that are still zero and silently returns a wrong total.
"Your bitmask solution: what is the largest input it handles?" Do the arithmetic out loud: 2^n n^2 is about 7 million at 15, about 420 million at 20, and memory for 2^n \times n entries is another limit. Candidates who cannot put a number on it have usually copied the pattern without understanding where the cost comes from.
"Can you do House Robber III with plain memoisation instead of pairs?" Yes: memoise "best total from this node" and, for the take case, recurse into the grandchildren. It works, but every node is reached from its parent and its grandparent, so you need a cache keyed by node. The pair version needs no cache because each node is visited exactly once. Explaining why the pair removes the cache is the signal of real understanding.
One thing to volunteer: all four shapes are shortest or longest paths on a graph of states, exactly as 4.22 section 8 argued, and the fill order is a topological order of that graph. For bitmask DP the order is simply "numbers ascending", because adding a member to a set always makes its mask bigger.
Recall
- 0/1 knapsack:
dp[i][c]= best value from the firstiitems in capacityc; skip (dp[i−1][c]) or take (dp[i−1][c−w] + v). Rolled to one row, a downward loop uses each item once, an upward loop reuses it (unbounded). - Knapsack is O(nC), which is pseudo-polynomial: polynomial in the value of the capacity, not in the input's length.
- Interval DP:
dp[i][j]over a range, try every splitkinside it, fill by increasing length; O(n^3), so expect small limits. - Bitmask DP: a set of up to ~20 items as the bits of an integer;
dp[mask][last]; fill masks in increasing order; O(2^n n^2). - Tree DP: post-order; each node returns exactly what its parent needs (for House Robber III, the pair robbed/skipped); O(n).
Self-test: Fill the knapsack table for one more item (1 kg, ₹5) and find the new answer · Why is the upward one-row loop the unbounded problem? · In the stick problem, why is filling row by row wrong? · What does mask 0b1011 mean in the delivery example, and which places can come next? · Why does the tree version need two numbers per node?
Next: 4.23 starts the dynamic programming problems with the one-dimensional ones, where the state is a single index and the whole skill is saying out loud what that index means.