Tabulation (bottom-up DP) — iterative: Question bank

Before we begin, three words we will lean on constantly — each was earned in the parent note:

True or false — justify

TF1. "Tabulation and memoization always have the same time complexity."

True — both compute each distinct subproblem exactly once; they only differ in how they reach the boxes (loop vs recursion), not in how many boxes exist. See Memoization (top-down DP).

TF2. "Tabulation is always faster than memoization in practice."

False — same asymptotic cost, but tabulation avoids call-stack overhead and may win by a constant factor. Memoization can be faster when it skips unreachable subproblems that tabulation still fills.

TF3. "Every recursive DP can be rewritten as tabulation."

True in principle — if you can list all subproblem parameters and order them so dependencies come first, you can loop them. The catch is finding that valid order.

TF4. "You must fill the base cases before the loop starts."

True — base cases are the boxes with no incoming arrows; the recurrence is undefined there. Without them the loop reads garbage or crashes on the first real box.

TF5. "If a table entry stays

0

after the algorithm, that always signals a bug."

False —

0

can be a legitimate answer (e.g. dp[i][c]=0 in 0-1 Knapsack when no item fits). Only an unexpected

0

where the recurrence should have fired is a bug.

TF6. "In tabulation you never need a recursion stack, so memory use is always lower than memoization."

False — you drop the call stack, but the table itself is the same size. Net memory is usually similar; the win is the stack, not the table.

TF7. "A problem with optimal substructure but no overlapping subproblems is a good tabulation candidate."

False — without overlap there is nothing to reuse; plain divide-and-conquer or greedy is simpler. Tabulation pays off precisely because the same box is needed many times.

TF8. "The final answer in tabulation is always in the last cell of the table."

False — usually it is (dp[n], dp[n][W]), but sometimes it is a max/sum over several cells (e.g. longest-run problems where the answer is

max_{i} d p [i]

TF9. "Climbing Stairs and Fibonacci share the same recurrence, so they are the same problem."

False — same recurrence shape

d p [i] = d p [i - 1] + d p [i - 2]

, but different base cases (dp[0]=1 for stairs vs dp[0]=0 for Fibonacci) and different meanings, so answers differ. Skeletons are reused; states are not.

Spot the error

SE1. "For Fibonacci I loop for i in range(n, 1, -1): dp[i]=dp[i-1]+dp[i-2]."

Wrong order — this fills large indices first, so dp[i-1] and dp[i-2] are still empty when read. Dependencies must be filled before they are read, so iterate small → large.

SE2. "1D knapsack: for c in range(W+1): dp[c]=max(dp[c], v+dp[c-w])."

The inner capacity loop goes low → high, so dp[c-w] was already overwritten in this pass — that reuses item

i

(unbounded knapsack behaviour). For 0/1 you must loop capacity high → low so dp[c-w] still holds the previous row. See Space Optimization in DP.

SE3. "I set dp[0]=0 for Climbing Stairs because there are zero ways to climb zero stairs."

Off-by-one on the meaning: dp[0] counts ways to be standing at step 0 (do nothing), which is exactly one way. Set dp[0]=1, else every count is halved.

SE4. "For knapsack I sized the table dp = [[0]*W for _ in range(n)]."

Two size bugs: capacity axis needs W+1 columns (indices

0 \dots W

), and the items axis needs n+1 rows so row

0

can hold the "no items" base case. Off-by-one here silently reads out of range or drops the base row.

SE5. "In the knapsack recurrence I wrote v_i + dp[i][c-w_i] for the take-case."

Should read the previous row dp[i-1][c-w_i] — after taking item

i

you may not consider it again, so you drop back to "first

i - 1

items". Reading the same row would let item

i

be reused.

SE6. "My recurrence reads dp[i-2] but I only initialised dp[0], and it works fine for n=1."

For n=1 the loop range(2, n+1) is empty, so the bug hides. It bites at n≥2 when dp[1] was never seeded and the first real iteration reads an unset box. Test the smallest non-trivial n, not just n=1.

SE7. "I filled the table correctly but returned dp[n-1] for Fibonacci where dp[i] is the

i

-th number."

Off-by-one on the answer cell. With dp[i] =

i

-th Fibonacci, the answer is dp[n], not dp[n-1]. Always re-read your Step-1 state sentence to locate the answer cell.

Why questions

WH1. "Why is Climbing Stairs a sum of two cases but 0/1 Knapsack a max?"

Stairs counts disjoint sets of paths (last move was a 1 or a 2 — no overlap), so we add. Knapsack chooses the best of two mutually exclusive options (take vs skip), so we maximise. Counting → add; optimising → min/max.

WH2. "Why must the fill order be the reverse of the recursive call order?"

Recursion starts big and asks downward for sub-answers; tabulation must produce those sub-answers first. So the direction that recursion descends is exactly the direction tabulation must ascend.

WH3. "Why does optimal substructure justify the recurrence at all?"

Optimal Substructure means an optimal whole is assembled from optimal parts. That is the license to write dp[big] in terms of dp[smaller] — otherwise combining sub-answers wouldn't give the true optimum. See Recurrence Relations.

WH4. "Why does tabulation 'never recompute' while plain recursion does?"

Plain recursion re-derives the same subproblem down every branch that needs it. Tabulation writes each box once and every later box reads that stored value — the reuse is what Dynamic Programming buys you.

WH5. "Why can we iterate the knapsack capacity in any order in the 2D version but not the 1D version?"

In 2D, every read is dp[i-1][...] — a different, already-complete row — so the current row's order is irrelevant. In 1D there is only one row, so read-order suddenly matters: high → low protects the previous-row values.

WH6. "Why do we even bother with tabulation if memoization gives the same complexity?"

No recursion depth limit (huge inputs won't overflow the stack), no call overhead, and the explicit table makes rolling-array tricks obvious. It trades a little upfront thinking about order for robustness.

WH7. "Why might tabulation waste work that memoization avoids?"

Tabulation fills every box in range, even ones no top-level query ever needs. Memoization only touches boxes actually requested. On sparse reachable states, top-down can do strictly less work.

Edge cases

EC1. "What does fib(0) return, and does the loop even run?"

Returns 0 via the n < 2 guard; the loop range(2, 1) is empty so it never executes. The guard exists precisely to handle n ∈ {0, 1} before any recurrence.

EC2. "Knapsack with capacity W = 0 — what is every answer?"

All dp[i][0] = 0: no capacity means nothing fits, so the take-branch condition w_i ≤ 0 is false for positive weights and we always skip. The whole first column stays the base value

0

EC3. "Knapsack where an item's weight exceeds W for all capacities — what happens to it?"

It never satisfies w_i ≤ c, so its row equals the row above it everywhere — the item is effectively invisible. Correct behaviour: an unusable item contributes nothing, no special-casing needed.

EC4. "Climbing Stairs with n = 0 — is the answer

0

1

It is 1 (dp[0]=1): the single "empty" way of already being at the bottom. Returning

0

here is the classic base-case sign error.

EC5. "Fibonacci for very large n in tabulation — what fails first, and how do we prevent it?"

The full dp array of size n+1 blows memory long before time is an issue; nothing overflows the stack because there's no recursion. Fix: collapse to two rolling variables (prev, curr) since only the last two boxes are ever read.

EC6. "A DP whose base case is a whole row or column, not a single cell — is tabulation still fine?"

Yes — you seed the entire base row/column before the main loop (e.g. dp[0][c]=0 across all c in knapsack). "Base case" just means every box with no incoming arrow, however many there are.

EC7. "What if two different fill orders both satisfy 'dependencies first' — does the answer change?"

No — any topological order of the dependency arrows yields identical table values, because each box's inputs are fixed regardless of when the other independent boxes were filled. Correctness depends on the order being valid, not unique.

EC8. "Negative or fractional indices in the recurrence (e.g. dp[i-2] at i=1) — how do we avoid reading them?"

Either guard with base cases that cover the smallest states, or start the loop at an index where all reads are in-range (range(2, ...)). An unguarded dp[-1] in Python silently reads the last element — a subtle, dangerous bug.

Connections

Tabulation (bottom-up DP) — iterative — the parent note these traps drill
Memoization (top-down DP) — contrast for TF1, TF2, WH2
Dynamic Programming — the paradigm; Optimal Substructure, Overlapping Subproblems — why the recurrence is legal
0-1 Knapsack, Coin Change, Longest Common Subsequence — sources of the take/skip and order traps
Space Optimization in DP — the high→low capacity trap (SE2, WH5)
Recurrence Relations — the math behind WH3