Tabulation (bottom-up DP) — iterative

WHAT is tabulation?

WHY does it work? A DP problem has optimal substructure (answer built from sub-answers) and overlapping subproblems (same sub-answers needed repeatedly). If we compute each subproblem once in an order where its dependencies are already done, we never recompute and never recurse.

HOW to build any tabulation (the recipe)

Deriving the canonical example: Fibonacci

We want $F(n)$ where $F(0)=0,\ F(1)=1,\ F(n)=F(n-1)+F(n-2)$.

Step 1 — State. dp[i] = the $i$-th Fibonacci number. Step 2 — Recurrence. By definition $dp[i]=dp[i-1]+dp[i-2]$. Why this step? Each Fibonacci number is literally the sum of the two before it — that IS the optimal substructure. Step 3 — Base cases. dp[0]=0, dp[1]=1. Step 4 — Order. Increasing $i$: when we compute dp[i], both dp[i-1] and dp[i-2] already exist. ✅ Step 5 — Answer. dp[n].

def fib(n):
    if n < 2: return n
    dp = [0]*(n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]   # read smaller, already filled
    return dp[n]

Worked example 2 — Climbing Stairs (counting paths)

You climb $n$ stairs, taking 1 or 2 steps at a time. How many distinct ways?

State. dp[i] = number of ways to reach step $i$. Recurrence. To land on step $i$, your last move was a 1-step (from $i-1$) or a 2-step (from $i-2$): $dp[i] = dp[i-1] + dp[i-2].$ Why this step? The set of ways splits cleanly by the last action; the two cases are disjoint, so we add them. Base. dp[0]=1 (one way: stand still), dp[1]=1. Answer. dp[n].

def climb(n):
    dp = [0]*(n+1)
    dp[0] = dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Same shape as Fibonacci — many DP problems share skeletons.

Worked example 3 — 0/1 Knapsack (2D table)

Items with weights $w_i$, values $v_i$, capacity $W$. Maximise value, each item used at most once.

State. dp[i][c] = best value using the first $i$ items with capacity $c$. Recurrence. For item $i$ (1-indexed, weight $w_i$, value $v_i$): $dp[i][c]=\begin{cases}dp[i-1][c] & \text{if } w_i>c\ (\text{can't take it})\\[4pt]\max\big(\underbrace{dp[i-1][c]}_{\text{skip}},\ \underbrace{v_i+dp[i-1][c-w_i]}_{\text{take}}\big)&\text{otherwise}\end{cases}$ Why this step? Every item is either in or out — that binary choice is the substructure. If we take it, capacity shrinks by $w_i$ and value grows by $v_i$, leaving a smaller subproblem dp[i-1][c-w_i]. Base. dp[0][c]=0 (no items → no value). Order. Increasing $i$ (rows), any order on $c$, because every read uses row $i-1$ which is fully done.

def knapsack(w, v, W):
    n = len(w)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]                     # skip item i
            if w[i-1] <= c:
                dp[i][c] = max(dp[i][c],
                               v[i-1] + dp[i-1][c-w[i-1]])  # take it
    return dp[n][W]

Common mistakes (steel-manned)

Active recall

Connections

• Memoization (top-down DP) — the recursive dual of this note
• Dynamic Programming — parent paradigm
• Optimal Substructure and Overlapping Subproblems — prerequisites
• 0-1 Knapsack, Longest Common Subsequence, Coin Change — classic tabulation problems
• Space Optimization in DP — rolling arrays from 2D tables
• Recurrence Relations — the math under the recurrence step

Concept Map

Hinglish (regional understanding)