Exercises — Tabulation (bottom-up DP) — iterative

The rule says each box = the two boxes just before it. WHAT we do: add dp[5] and dp[4]. WHY: the recurrence dp[6]=dp[5]+dp[4] — both are already filled, so we may read them. $dp[6]=5+3=\boxed{8}.$

Starting big and recursing down = memoization (top-down). See Memoization (top-down DP). Tabulation is the opposite: start at the smallest boxes and loop upward. Both compute each subproblem once; only the travel direction differs.

Answer cell: the largest state, dp[4]. Base cases: dp[0]=1 (one way — stand still) and dp[1]=1 (one way — a single 1-step). Filling upward: dp[2]=2, dp[3]=3, dp[4]=5.

Seed: dp[0]=0, dp[1]=1. Loop small→large, each box = sum of previous two:

$dp[7]=dp[6]+dp[5]=8+5=\boxed{13}.$

State: dp[a] = number of combinations summing to a. Base: dp[0]=1 (one way to make 0 — pick nothing). WHY coins outside: to count combinations (not permutations), we must commit to one coin denomination fully before the next, so {1,2} and {2,1} are not double-counted.

Start dp = [1,0,0,0,0,0].

Process coin 1 (each amount gains ways from a-1): dp = [1,1,1,1,1,1]. Process coin 2 (each a≥2 gains from a-2):

• dp[2]+=dp[0]=1 → 2
• dp[3]+=dp[1]=1 → 2
• dp[4]+=dp[2]=2 → 3
• dp[5]+=dp[3]=2 → 3

Final dp = [1,1,2,2,3,3], so $\boxed{dp[5]=3}$. The three ways: 1+1+1+1+1, 1+1+1+2, 1+2+2. ✅

Recurrence: try each coin as the last one used: $dp[i]=1+{\min }_{\text{coin}\le i}dp[i-\text{coin}],dp[0]=0.$ WHY min, not sum: here we optimize a quantity (fewest coins), so we pick the best last choice — contrast with L2.2 where we count and therefore add.

Build upward:

Check dp[6]: candidates 1+dp[5]=3, 1+dp[3]=2, 1+dp[2]=3. Minimum is $\boxed{2}$ (i.e. 3+3).

Rows = items considered (0 = none); columns = capacity c from 0 to 4. Row 0 is all zeros (no items → no value).

Row 1 — item (1,1): for c≥1 we may take it. dp[1][c]=max(0, 1+dp[0][c-1])=1. [0, 1, 1, 1, 1]

Row 2 — item (3,4): takeable when c≥3.

• c=0,1,2: too heavy → copy above → 0,1,1
• c=3: max(dp[1][3]=1, 4+dp[1][0]=4)=4
• c=4: max(dp[1][4]=1, 4+dp[1][1]=5)=5 [0, 1, 1, 4, 5]

Row 3 — item (4,5): takeable only at c=4.

• c=0..3: copy above → 0,1,1,4
• c=4: max(dp[2][4]=5, 5+dp[2][0]=5)=5 [0, 1, 1, 4, 5]

$\boxed{dp[3][4]=5.}$ Two optimal packings tie at value 5: item 3 alone, or items 1+2 (1+4).

Every entry dp[i][c] reads row i-1. If we fill row n first, row n-1 is still all zeros → we read garbage. WHAT breaks: dependencies are read before they exist. The rule: iterate so each cell's inputs are already filled. Since dp[i] depends on dp[i-1], we must go small i → large i. The order is dictated by the arrows in the recurrence, never by taste.

Correct: high→low. See Space Optimization in DP.

The 1D update is dp[c] = max(dp[c], v + dp[c-w]), where dp[c-w] must mean the previous row (item not yet used).

Low→high (WRONG): start dp=[0,0,0,0,0], item (2,3).

• c=2: dp[2]=max(0,3+dp[0])=3
• c=4: dp[4]=max(0,3+dp[2])=3+3=6 ← used the item twice! (unbounded, not 0/1)

High→low (RIGHT):

• c=4: dp[4]=max(0,3+dp[2]=3+0)=3
• c=2: dp[2]=max(0,3+dp[0])=3
• final dp=[0,0,3,0,3] → best value 3, item used once. ✅

Going high→low guarantees dp[c-w] was not yet overwritten this round, so it still holds the previous row.

State: dp[i][j] = LCS length of A[0..i) and B[0..j). Base: dp[0][j]=dp[i][0]=0 (empty string shares nothing). Recurrence: $dp[i][j]=\{\begin{array}{ll}dp[i-1][j-1]+1& A_i=B_j(\text{matched letter extends the LCS})\\ \max (dp[i-1][j],dp[i][j-1])& A_i\ne B_j(\text{drop one letter, keep the better side})\end{array}$ WHY: if the last letters match, they can end a common subsequence, so we take the LCS of everything before them and add 1. If not, at least one of the two last letters is unused → try dropping each and keep the larger.

Filling the grid (rows = letters of A, cols = letters of B), the final cell is: $\boxed{dp[7][5]=4.}$ One such LCS of length 4 is "BCAB" (or "BDAB").

State: dp[i] = best total using houses 0..i under the no-two-adjacent rule. Recurrence: for house i, either skip it (dp[i-1]) or take it (cost[i] + dp[i-2], since i-1 is now forbidden): $dp[i]=\max (dp[i-1],cost[i]+dp[i-2]).$ Base: dp[0]=cost[0]=2, dp[1]=max(cost[0],cost[1])=7.

• dp[2]=max(7, 9+2)=11
• dp[3]=max(11, 3+7)=11
• dp[4]=max(11, 1+11)=12

$\boxed{dp[4]=12}(\text{houses }2+7+\dots \text{ actually }2+9+1=12).$

Bug: they initialised every cell to 0, but only dp[0] should be 0. Every other cell must start at "impossible" = a large sentinel (e.g. amount+1 or float('inf')). Why it feels right: 0 is the natural empty value and matches the true dp[0]. What breaks: the recurrence dp[i]=1+min(dp[i-coin]) reads other cells; if they are 0, the min wrongly believes any amount is reachable with almost no coins, poisoning everything. Fix: $dp=[0,\infty ,\infty ,\dots ],dp[0]=0.$ A cell still equal to ∞ at the end means "amount unreachable". Base cases seed the table; a wrong seed is as fatal as a missing one.

Naive recursion re-enters the same subproblem through different call paths (the Overlapping Subproblems property), so F(n) can spawn $O({\phi }^n)$ calls. Tabulation visits each cell in a single loop pass. Formally: the outer loop index takes each value in its range once; each cell is written exactly once (in its loop iteration) and thereafter only read. Because we order the loop so dependencies precede the cell (Optimal Substructure guarantees dependencies are smaller states), no cell is ever revisited to compute it. Result: total work = (number of cells) × (cost per cell). For Fibonacci that is $O(n)$ vs the exponential recursion.

The rule: Iterate so that every cell you read during an update still holds the value from the intended prior stage — not a value already overwritten this pass.

• If reads reference strictly earlier, never-overwritten cells (Fibonacci with rolling vars) → direction is free.
• If a read dp[c-w] and the write dp[c] live in the same array being overwritten this round, choose the direction that visits the read location after the write location, so the read still sees the old value. For knapsack, c-w < c, so writing high→low keeps dp[c-w] untouched until later. ✅

This is exactly the Space Optimization in DP safety condition, and it subsumes every mistake in the parent note.

Every problem here was the same four moves: name the box (state), write the fill rule (recurrence), hand-fill the boxes no rule reaches (base), and loop so a box's ingredients are ready before you cook it (order). Counting problems add; best/least problems take min/max; in-place tricks live or die by loop direction. That's the whole ladder.