Two Dimensional DP and Knapsack

Some DP states need two dimensions to describe them — not just “which index,” but “which index, and how much capacity/budget/count is left.” The knapsack family is the canonical example, and once you can read its 2D table, subset-sum and partition problems fall out of the same recurrence with a small twist.

What you’ll learn

• The 0/1 knapsack recurrence: for each item, take it or leave it.
• How to read the 2D table dp[i][w] — “best value using the first i items with capacity w.”
• Unbounded knapsack: the same table, but items can be reused.
• Subset sum / Partition Equal Subset Sum: knapsack with a boolean instead of a max.
• Space optimization: collapsing the 2D table to a single rolling 1D array.

The cue

You are looking at 2-D DP when…

• There are two things that both vary: an item index and a remaining capacity; a position in string A and a position in string B; a row and a column.
• One index alone cannot express the state. The test: try writing “dp[i] is …” and notice that the sentence needs a second “with … remaining” or “against …” clause. That clause is your second dimension.
• The problem is take-it-or-leave-it under a budget — capacity, amount, number of operations, number of transactions.
• You are comparing two sequences — edit distance, longest common subsequence, matching with wildcards.

The reframe: a 2-D table is not “harder DP”, it is the same recurrence with the choice made explicit. dp[i][w] asks one question — skip item i, or take it and drop to capacity w − wt? — and each option names exactly one cell to read. Draw a 3×4 grid by hand and fill it once; the code then writes itself.

Reach for something else when the second dimension is a set rather than a number (bitmask DP, $n \le 20$), when the budget is huge ($10^{12}$ capacity makes the table impossible — knapsack is NP-hard and $O(nW)$ is only pseudo-polynomial), or when one index really is enough (1-D DP — do not add a dimension defensively).

0/1 Knapsack

Given item weights, values, and a capacity W, maximize total value without exceeding the capacity — each item can be used at most once. State: dp[i][w] = best value achievable using the first i items with capacity w. For each item, either skip it (dp[i-1][w]) or take it (if it fits) and add its value to the best from the remaining capacity.

$$dp[i][w] = \begin{cases} dp[i-1][w] & wt_i > w \\ \max\big(dp[i-1][w],\ dp[i-1][w - wt_i] + val_i\big) & wt_i \le w \end{cases}$$

knapsack_01.py

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                    # option 1: skip item i
            if wt <= w:
                take = dp[i - 1][w - wt] + val          # option 2: take item i
                dp[i][w] = max(dp[i][w], take)
 
    return dp[n][capacity]
 
 
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(knapsack_01(weights, values, 7))   # expect 9  (items of weight 3 + 4 -> value 4 + 5)

Reading the table: row i is “using only the first i items,” column w is “with this much capacity.” dp[i][w] always equals at least dp[i-1][w] (taking item i can only help, never hurt), so the table grows monotonically down each column. The final answer sits in the bottom-right corner: all items considered, full capacity available.

Unbounded Knapsack

Same setup, but now each item can be used any number of times (think: coin change, but maximizing value instead of counting ways). The only change from 0/1: when you take an item, you stay on row i (not i - 1), because item i is still available to take again.

$$dp[i][w] = \max\big(dp[i-1][w],\ dp[i][w - wt_i] + val_i\big)$$

knapsack_unbounded.py

def knapsack_unbounded(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                    # option 1: skip item i entirely
            if wt <= w:
                take = dp[i][w - wt] + val              # option 2: reuse item i again (stay on row i)
                dp[i][w] = max(dp[i][w], take)
 
    return dp[n][capacity]
 
 
weights = [2, 3, 4]
values = [3, 4, 5]
print(knapsack_unbounded(weights, values, 7))   # expect 10  (two of weight 2 + one of weight 3 -> 3+3+4)

Subset Sum / Partition Equal Subset Sum

Can a subset of the array sum to exactly some target? This is knapsack with values dropped entirely — dp[i][s] is now a boolean: “can the first i numbers reach sum s?” Partition Equal Subset Sum asks whether the whole array can be split into two equal-sum halves, which is just subset sum with target = total_sum / 2.

$$dp[i][s] = dp[i-1][s] \ \lor\ \big(s \ge num_i \ \land\ dp[i-1][s - num_i]\big)$$

partition_equal_subset_sum.py

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False                 # an odd total can never split into two equal halves
    target = total // 2
 
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True               # sum 0 is always reachable: take nothing
 
    for i in range(1, n + 1):
        num = nums[i - 1]
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]                        # skip nums[i-1]
            if num <= s:
                dp[i][s] = dp[i][s] or dp[i - 1][s - num]   # or use it
 
    return dp[n][target]
 
 
print(can_partition([1, 5, 11, 5]))   # expect True   ({1, 5, 5} and {11})
print(can_partition([1, 2, 3, 5]))    # expect False  (no equal split exists)

Watching the table fill

sketch 0/1 knapsack table filling row by row p5.js Pause Restart

Each cell only reads the row above it (skip) and a cell to the upper-left within reach (take) -- never a cell in a row below.

Space optimization: 2D table to a rolling 1D array

Look at the 0/1 knapsack recurrence again: row i only ever reads row i - 1. You never need more than the previous row in memory, so the full (n + 1) x (W + 1) table can shrink to a single array of size W + 1 — as long as you iterate w from high to low for 0/1 knapsack (so dp[w - wt] still holds “last row’s” value, not an already-updated “this row’s” value):

knapsack_01_rolling.py

def knapsack_01_rolling(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):   # right to left: reuse last row's values
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]
 
 
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(knapsack_01_rolling(weights, values, 7))   # expect 9 -- same answer, O(W) space

For the unbounded knapsack, the loop direction flips to low-to-high, since reusing “this row’s” already-updated value is exactly the point (an item can be picked again). Same rule applies to subset sum: iterate s high to low to keep each number used at most once.

Dry run

0/1 knapsack — weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7. Row i means “only the first i items are available”; column w is the capacity on hand.

row	w=0	1	2	3	4	5	6	7
0 items	0	0	0	0	0	0	0	0
1 (w1 v1)	0	1	1	1	1	1	1	1
2 (w3 v4)	0	1	1	4	5	5	5	5
3 (w4 v5)	0	1	1	4	5	6	6	9
4 (w5 v7)	0	1	1	4	5	7	8	9

Answer 9, in the bottom-right — the items of weight 3 and 4, values 4 + 5.

• Row 0 is not padding. “No items available” genuinely scores 0 at every capacity, and having that row is what lets row 1 read dp[i-1][…] without a special case. Indexing items from 1 while the arrays are 0-based (weights[i-1]) is the price, and the most common source of off-by-one bugs here.
• dp[2][4] = 5, not 4. Capacity 4 fits both item 1 (w1) and item 2 (w3): 1 + 4 = 5. Read it as dp[1][4-3] + 4 = dp[1][1] + 4 = 5. That single cell shows the recurrence combining two items without ever enumerating subsets.
• The last row barely changes. Item 4 (weight 5, value 7) improves capacities 5 and 6 — 7 beats 6, 8 beats 6 — but at capacity 7 the existing 9 already wins, because 3 + 4 packs better than 5 alone. The greedy “best value per weight first” instinct picks item 4 (1.4/unit) and lands on 8. The table’s 9 is the reason knapsack is not greedy.
• Every column is non-decreasing downward, since more items available can never hurt. If a cell ever drops going down a column, the recurrence has a bug — a useful invariant to check by hand.

Unbounded, same input: the final row becomes 0 1 2 4 5 7 8 9. Compare w = 2: 0/1 gives 1 (only one item of weight 1 exists), unbounded gives 2 (use it twice). The only code difference is dp[i][w - wt] instead of dp[i-1][w - wt] — stay on the current row so the item is still available. One index.

Complexity

Let n be the number of items and W the capacity (or m, n the two string lengths).

Variant	Time	Space
0/1 knapsack, full table	$O(nW)$	$O(nW)$
0/1 knapsack, two rows	$O(nW)$	$O(W)$
0/1 knapsack, one row (capacity descending)	$O(nW)$	$O(W)$ — see knapsack variants
Unbounded knapsack	$O(nW)$	$O(W)$, capacity ascending
Subset sum / partition	$O(nS)$	$O(S)$ booleans
Two-sequence DP (LCS, edit distance)	$O(mn)$	$O(\min(m, n))$ with rolling rows
Recovering the chosen items	$O(nW)$	$O(nW)$ — the full table is required

$O(nW)$ is pseudo-polynomial — say this before you are asked

The bound is polynomial in the value of W, not in the number of digits it takes to write it. A capacity of $10^9$ with three items is intractable; a capacity of 1000 with 200 items is instant. Knapsack is NP-hard, and this DP is only efficient because interview constraints keep W small.

If asked “what if the capacity is $10^{12}$?”, the answer is not a bigger array: it is meet-in-the-middle at $O(2^{n/2})$ for small n, branch and bound, or an FPTAS approximation. Recognising that the algorithm has a range of applicability rather than being universally correct-and-fast is the point.

The variant map

Problem	Second dimension	Transition	The one thing that changes
0/1 knapsack	remaining capacity	max(dp[i-1][w], dp[i-1][w-wt] + val)	the baseline
Unbounded knapsack	remaining capacity	max(dp[i-1][w], dp[i][w-wt] + val)	take stays on row i
Bounded (k copies)	capacity	—	binary-split each item into $1,2,4,\dots$ copies, then run 0/1
LC 416 Partition Equal Subset Sum	target sum	booleans, dp[i][s] or dp[i-1][s-n]	odd total → False immediately
LC 494 Target Sum	subset sum	counting instead of max	sign transform: subsets summing to (total+target)//2
LC 474 Ones and Zeroes	two capacities	dp[m][n]	a genuine 3-D table; both capacities descend when collapsed
LC 1143 LCS	index in the second string	dp[i-1][j-1] + 1 on a match, else max of the two neighbours	two sequences, not items and capacity
LC 72 Edit Distance	index in the second string	1 + min of three neighbours	three options (insert/delete/replace), not two
LC 64 Min Path Sum	column	grid + min(up, left)	the grid is the table
LC 123/188 stock with k transactions	transactions remaining	—	see DP on stocks; the second dimension is a budget of trades
Which items were chosen	—	—	keep the full table and walk backwards: if dp[i][w] != dp[i-1][w], item i was taken

Pitfalls

• Off-by-one between rows and items. Row i uses weights[i-1]. Mixing the two indexings gives an answer that is wrong by exactly one item, usually the last.
• Dropping the zero row or zero column. They are the base cases, not padding. Without them every read of dp[i-1][…] needs a guard, and one of those guards will be forgotten.
• Using dp[i-1][w-wt] for unbounded (or dp[i][w-wt] for 0/1). The row index is the reuse rule; nothing else distinguishes the two problems.
• Collapsing to one array and iterating capacity ascending for 0/1. That silently turns it into unbounded — an item gets reused and the answer comes out too large. Descending for 0/1, ascending for unbounded.
• Assuming greedy works. On the dry-run input, “best value per unit weight” picks item 4 and returns 8 instead of 9. Fractional knapsack is greedy; the 0/1 version is not, and that difference is a favourite interview probe.
• Returning the wrong cell. The answer is dp[n][capacity] (all items, full capacity) — not max(dp[n]), and not dp[n][-1] on a table you have already collapsed.
• Forgetting that values can be zero or items can be heavier than the capacity. An item with wt > capacity must never be taken; the if wt <= w guard is what enforces it, and removing it produces negative indices that wrap silently in Python.
• Optimising space before the recurrence is right. Get the 2-D version correct, verify it by hand on a 4×8 table, and only then collapse. Debugging a collapsed array whose recurrence was wrong to begin with is the worst of both worlds.

Interview follow-ups

They ask	What they’re checking	The answer
“Why not take the highest value-per-weight item first?”	Whether you know knapsack is not greedy	Because 0/1 items are indivisible. On weights=[1,3,4,5], values=[1,4,5,7], capacity 7, greedy takes the 5/7 item and scores 8; the optimum is 3 + 4 = 9. Fractional knapsack is greedy — the difference is whether you may take part of an item
“Reduce the space”	The standard optimisation	Each row depends only on the row above, so two rows suffice — and one row does, if capacity is iterated descending so dp[w-wt] still holds the previous row’s value
“Now tell me which items you packed”	The cost of that optimisation	The collapsed array has discarded it. Keep the full table and walk back from dp[n][W]: whenever dp[i][w] != dp[i-1][w], item i was taken, so subtract its weight and continue
“What is the complexity, and is it polynomial?”	Precision	$O(nW)$ time — pseudo-polynomial, since it is linear in the value of W rather than its digit count. Knapsack is NP-hard; this is efficient only for small W
“The capacity is 10^12”	Boundaries	The table is impossible. Meet-in-the-middle $O(2^{n/2})$ for small n, branch and bound, or an approximation scheme — not a larger array
“Each item has a limit of 3 copies”	Generalisation	Binary-split each item into copies of size $1, 2, 4$ (weights and values scaled), then run plain 0/1. That gets bounded knapsack in $O(nW\log k)$ rather than $O(nWk)$
“Two constraints — weight and volume”	Whether the pattern extends	Add a dimension: dp[i][w][v]. LC 474 is exactly this with counts of zeros and ones, and when collapsed both capacity loops descend
“Same table for edit distance?”	Recognising the shape	Yes — the second dimension becomes the index in the second string, and the transition takes min over three neighbours instead of max over two. Same table, different question

Practice — real LeetCode problems

Three knapsacks with three different flavours: unbounded (reuse allowed), 0/1 with two capacities at once, and a minimisation that only becomes a knapsack after you rewrite the question.

LC 322 — Coin Change · Medium

Problem. Given coin denominations and an amount, return the fewest coins that sum to exactly amount, or -1 if it is impossible. You have unlimited coins of each denomination.

Constraints. 1 <= len(coins) <= 12, 1 <= coins[i] <= 2**31 - 1, 0 <= amount <= 10**4.

Examples. coins = [1,2,5], amount = 11 gives 3 (5+5+1) · coins = [2], amount = 3 gives -1 · amount = 0 gives 0

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Unbounded knapsack, minimising count. The direction of the capacity loop is the whole distinction:

• Ascending capacity: dp[a - c] may already include coin c, so coins are reusable — unbounded.
• Descending capacity: dp[a - c] is from the previous item’s row, so each coin is used at most once — 0/1.

Time $O(\text{amount} \times \text{len(coins)})$. Space $O(\text{amount})$.

• amount = 0 returns 0, and dp = [0] handles it with no loop iterations.
• Greedy largest-first fails. coins = [1,3,4], amount = 6 greedily takes 4+1+1 = 3 coins; the answer is 3+3 = 2. Greedy is only correct for canonical systems, and real currency happens to be one — which is why the intuition is so sticky and so wrong here.
• Unreachable amounts must return -1, not infinity. [2] with amount = 3 is the check.
• Huge denominations are harmless: the c <= a guard skips any coin bigger than the current amount, so 2**31 - 1 never indexes out of range.

Follow-ups you should expect: “Which coins?” — store the coin that improved each dp[a] and walk back from amount. “Count the combinations instead (LC 518)?” — loop coins outside and amounts inside, and sum; the loop order is what stops permutations being double-counted. “Count permutations (LC 377)?” — swap those loops. “At most k of each coin?” — bounded knapsack, solved with binary splitting of the counts. “Amount up to $10^9$?” — the DP dies and it becomes a number-theory problem.

LC 474 — Ones and Zeroes · Medium

Problem. Given an array of binary strings and budgets m (zeros) and n (ones), return the size of the largest subset of strings whose total zero count is at most m and total one count is at most n.

Constraints. 1 <= len(strs) <= 600, 1 <= len(strs[i]) <= 100, 1 <= m, n <= 100.

Examples. strs = ["10","0001","111001","1","0"], m = 5, n = 3 gives 4 (the subset ["10","0001","1","0"]) · strs = ["10","0","1"], m = 1, n = 1 gives 2

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The tell is “at most m zeros and at most n ones”: two independent resources, so the capacity is a pair. Everything else is standard 0/1 knapsack with every item’s value equal to 1.

Time $O(\text{len(strs)} \times m \times n)$ — about $600 \times 100 \times 100 = 6 \times 10^6$ here. Space $O(mn)$.

• Both loops must descend. If either ascends, a string can be reused inside its own pass and you overcount. The given examples will not catch the bug — both loop directions answer [4, 2, 2]. The smallest input that does is ["0"] with m = 2, n = 1: the answer is 1, and an ascending loop says 2, having spent the single string twice.
• The item loop stays outermost. Rolling a 2D array in place only works because each string is fully processed before the next begins.
• A string that fits neither budget is skipped automatically: `range(m, zeros
  • 1, -1)is empty whenzeros > m`, so no guard is needed.
• m or n equal to 0 is outside LeetCode’s constraints, but the code still handles it — the grid is a single row or column and only free items would fit.

Follow-ups you should expect: “Which strings?” — keep the full 3D table dp[k][i][j] and backtrack, or store parents. “Maximise total length instead of count?” — the item value becomes len(s); nothing else changes. “Three resources?” — a third descending loop, and the constant factor stops being friendly. “Can this be greedy by shortest string first?” — no; a short string may eat the one zero a much better pair needed.

LC 1049 — Last Stone Weight II · Medium

Problem. Repeatedly smash two stones x and y: both are destroyed and, if x != y, a stone of weight |x - y| is added. Return the smallest possible weight of the last remaining stone (0 if none remains).

Constraints. 1 <= len(stones) <= 30, 1 <= stones[i] <= 100.

Examples. [2,7,4,1,8,1] gives 1 · [31,26,33,21,40] gives 5

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The reduction is the interview. Once you see that every schedule assigns each stone a + or a -, the problem reads: split the stones into groups $A$ and $B$ minimising $|{\sum A} - {\sum B}|$. Writing $\sum A = b$ and $\sum B = \text{total} - b$, the difference is $\text{total} - 2b$, minimised by the largest $b \le \lfloor \text{total}/2 \rfloor$ you can actually reach. That is subset sum.

Why the reduction holds, in both directions: any schedule expands into a signed sum by induction on the smashes, and conversely any sign assignment is realisable — smash within each group down to one stone each, then smash those two together. The total - 2b form with b <= total // 2 also guarantees the result is non-negative, so no absolute value is needed.

Time $O(n \times \text{total})$, at most $30 \times 3000$. Space $O(\text{total})$.

• total // 2 floors, which is what you want: for an odd total the two groups cannot tie and the best difference is 1.
• [1,1] gives 0 — the two stones annihilate. [1] gives 1 — nothing to smash, so total - 2 * 0.
• The r + s <= target filter is what keeps the set small and is also why max(reachable) is the right pick; without the cap you would need the value nearest to half from below.
• Building a new set inside the comprehension is the set-based equivalent of the descending loop: you must not iterate a set you are mutating, and you must not let stone s be added twice.

Follow-ups you should expect: “How is this different from LC 1046, Last Stone Weight?” — that one fixes the schedule as always-smash-the-two-largest, so it is a heap problem, not DP. Knowing why the greedy is correct there and wrong here is the point. “Return the two groups?” — track predecessors, or use a boolean table instead of a set. “Bitset trick?” — bits |= bits << s, then scan down from target for the highest set bit; Python’s big ints make this very fast. “All stones equal?” — the answer is 0 for an even count, stones[0] for an odd one.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

8 problems

0 easy6 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○97Interleaving StringmediumNeetCode 150LeetCode Top Interview 150
• ○309Best Time to Buy and Sell Stock with CooldownmediumNeetCode 150
• ○416Partition Equal Subset SummediumSubset sum with `target = total / 2`, as aboveNeetCode 150
• ○474Ones and ZeroesmediumKnapsack with **two** capacity dimensions (count of 0s and count of 1s) instead of one
• ○494Target SummediumAssign `+`/`-` signs to reach a target; reframes into a subset-sum problem once you do the algebra on positive vs. negative subsetsNeetCode 150
• ○1049Last Stone Weight IImediumReframes into "find the subset closest to half the total," minimizing the leftover difference
• ○123Best Time to Buy and Sell Stock IIIhardLeetCode Top Interview 150
• ○188Best Time to Buy and Sell Stock IVhardLeetCode Top Interview 150

Self-check

pch.quizTag Two-dimensional DP and knapsack — self-check

1. How do you know a problem needs two dimensions rather than one?

   A Whenever the input is an array of pairs B When the sentence 'dp[i] is …' cannot be completed without a second clause — 'with w capacity remaining', 'against index j of the other string'. That clause is the second dimension C When n is large D Whenever the answer is a maximum
   pch.quizShowAnswer

   B — When the sentence 'dp[i] is …' cannot be completed without a second clause — 'with w capacity remaining', 'against index j of the other string'. That clause is the second dimension — Writing the state sentence first is the actual technique. Adding a dimension defensively costs O(nW) space for nothing; failing to add a needed one produces a recurrence that cannot be written at all.

2. What is the ONLY difference between 0/1 and unbounded knapsack in the 2-D form?

   A Unbounded needs a third dimension B The row you read when taking the item: dp[i-1][w-wt] for 0/1 (item consumed) versus dp[i][w-wt] for unbounded (item still available) C Unbounded iterates capacity descending D Unbounded initialises the first row to infinity
   pch.quizShowAnswer

   B — The row you read when taking the item: dp[i-1][w-wt] for 0/1 (item consumed) versus dp[i][w-wt] for unbounded (item still available) — One index. In the collapsed one-array form the same distinction appears as descending versus ascending capacity, which is why deriving it from 'has this cell been written yet' is more reliable than memorising.

3. On weights [1,3,4,5], values [1,4,5,7], capacity 7, greedy by value-per-weight returns 8 but the answer is 9. Why?

   A Greedy has a bug B Because 0/1 items are indivisible: taking the best-ratio item (weight 5) wastes the remaining capacity, while 3 + 4 fills it exactly. Fractional knapsack IS greedy — the difference is whether you may take part of an item C Because the values are too small D Because greedy needs the items sorted by weight
   pch.quizShowAnswer

   B — Because 0/1 items are indivisible: taking the best-ratio item (weight 5) wastes the remaining capacity, while 3 + 4 fills it exactly. Fractional knapsack IS greedy — the difference is whether you may take part of an item — This is the standard probe for whether you understand why a DP is required. Being able to name the fractional variant as the case where greedy is provably optimal is what makes the answer convincing.

4. You collapse the table to one array. Which capacity direction, and why?

   A Ascending for 0/1, descending for unbounded B Descending for 0/1 — so dp[w - wt] still holds the previous row's value and the item is used once; ascending for unbounded, so it may be reused C Always ascending D It does not matter once the table is correct
   pch.quizShowAnswer

   B — Descending for 0/1 — so dp[w - wt] still holds the previous row's value and the item is used once; ascending for unbounded, so it may be reused — Getting this backwards silently converts one problem into the other — no crash, an answer that is too large. Derive it from 'has this index been overwritten this round?'

5. Is O(nW) polynomial?

   A Yes, it is linear in both inputs B No — it is pseudo-polynomial: linear in the VALUE of W rather than in the number of digits needed to write it. Knapsack is NP-hard, and this DP is efficient only while W is small C Yes, because W is bounded by the item weights D Only when the weights are distinct
   pch.quizShowAnswer

   B — No — it is pseudo-polynomial: linear in the VALUE of W rather than in the number of digits needed to write it. Knapsack is NP-hard, and this DP is efficient only while W is small — Three items with a capacity of 10^9 is intractable; 200 items with capacity 1000 is instant. That asymmetry is the whole content of 'pseudo-polynomial'.

6. The follow-up asks which items you packed. What changes?

   A Nothing — read them off the final row B You need the full O(nW) table back: walk from dp[n][W] and whenever dp[i][w] != dp[i-1][w], item i was taken, so subtract its weight and continue C Sort by value and re-run D Store a set of items inside each cell
   pch.quizShowAnswer

   B — You need the full O(nW) table back: walk from dp[n][W] and whenever dp[i][w] != dp[i-1][w], item i was taken, so subtract its weight and continue — Storing a set per cell also works and is what people reach for first, but it costs O(nW · n) memory. The backwards walk is free once you have kept the table.

Recall card

• Cue — two things vary at once: item and capacity, or index in A and index in B. Test it by trying to write the state as one sentence.
• 0/1 — dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt] + val). Unbounded — take reads dp[i][w-wt], staying on the current row. That single index is the whole difference.
• Row 0 and column 0 are real base cases — “no items” and “no capacity” both score 0, and keeping them removes every boundary guard.
• Answer is dp[n][capacity], the bottom-right corner.
• Columns never decrease downward — a handy invariant when debugging by hand.
• Space — two rows always; one row if capacity iterates descending for 0/1, ascending for unbounded. Collapse after the recurrence is verified, never before.
• Cost — $O(nW)$, pseudo-polynomial. Fine for $W \le 10^5$; hopeless at $10^{12}$.
• Not greedy — value-per-weight fails on 0/1 (8 instead of 9 on the dry-run input); fractional knapsack is the version where greedy is provably optimal.
• Recovering the items needs the full table plus a backwards walk.

Recap

• 2D DP states show up when the answer depends on two things changing together — here, “how many items considered” and “how much capacity remains.”
• 0/1 knapsack: each item taken at most once — the “take” branch reads the row above (dp[i-1][...]).
• Unbounded knapsack: items reusable — the “take” branch reads the same row (dp[i][...]), since the item can be picked again.
• Subset sum / Partition Equal Subset Sum: knapsack with a boolean instead of a max — “is this sum reachable?” instead of “what’s the best value?”
• A 2D table that only ever reads the row directly above (or the same row) collapses to a rolling 1D array — iterate capacity high-to-low for 0/1 (each item once), low-to-high for unbounded (items reusable).

That covers the “index-based” core of dynamic programming: spotting DP from a recursion tree, solving it with a 1D state, and scaling up to a two-dimensional state with knapsack. The state doesn’t have to stop at an index, though.

Next: Classic DP: LIS, LCS, and Edit Distance — three more foundational recurrences, this time over sequences.