Tabulation

What Is Tabulation?

Tabulation is the bottom-up approach to DP: fill a table iteratively starting from the smallest sub-problems, building toward the final answer without any recursion.

THE CORE DIFFERENCE FROM MEMOIZATION:

MEMOIZATION (top-down):           TABULATION (bottom-up):
  Start from the question.          Start from the answers.
  Recurse toward base cases.        Fill base cases first.
  Cache results along the way.      Build up to the final answer.
  Lazy — only needed states.        Eager — ALL states in table.

BOTH produce the same answer.
Both have the same time complexity.
Tabulation is usually faster in practice (no recursion overhead).

TABULATION STRUCTURE:
  1. Declare table: dp[0..n] or dp[0..m][0..n]
  2. Fill base cases: dp[0] = ..., dp[1] = ...
  3. Fill remaining cells in dependency order
  4. Return answer: dp[n] or dp[m-1][n-1]

Conversion Recipe: Memoized → Tabulated

STEP-BY-STEP RECIPE:

MEMOIZED:                         TABULATED:
  ① declare cache                   ① declare table (same shape as cache)
  ② base case checks inside fn      ② explicit base case fills BEFORE loop
  ③ cache check                     (no cache check needed)
  ④ recursive calls                 ③ direct table lookups dp[i-1], dp[i-2]
  ⑤ store result                    (automatic — loop fills in order)
  ⑥ return result                   ④ return final cell dp[n] or dp[m][n]

TRANSLATION RULES:
  fib(n-1)          →  dp[i-1]     (recursive call → table cell)
  fib(n-2)          →  dp[i-2]
  memo[n] = result  →  dp[i] = ... (store stays, no cache check needed)
  return memo[n]    →  (implicit — loop fills sequentially)

Conversion Example: Fibonacci

MEMOIZED:                              TABULATED:

memo = [-1] * (n+1)                    dp = [0] * (n+1)
                                        dp[0] = 0    ← base case from: if n<=1
def fib(n, memo):                       dp[1] = 1    ← base case from: if n<=1
    if n <= 1: return n      ┐
    if memo[n] != -1:        │          for i in range(2, n+1):
        return memo[n]       ├──────→       dp[i] = dp[i-1] + dp[i-2]
    memo[n] = fib(n-1,memo)  │
            + fib(n-2,memo)  ┘          return dp[n]
    return memo[n]

WHAT CHANGED:
  - Recursive calls fib(n-1) and fib(n-2) → direct lookups dp[i-1] and dp[i-2]
  - Cache check (if memo[n] != -1) → removed (loop fills in order, no stale reads)
  - Base case inside function → explicit assignment dp[0]=0, dp[1]=1 before loop
  - return memo[n] → return dp[n] (single location after loop)

FILL ORDER visualised:
  i=0: dp[0]=0  (base)
  i=1: dp[1]=1  (base)
  i=2: dp[2]=dp[1]+dp[0]=1
  i=3: dp[3]=dp[2]+dp[1]=2
  i=4: dp[4]=dp[3]+dp[2]=3
  i=5: dp[5]=dp[4]+dp[3]=5
  ...
  When computing dp[i], both dp[i-1] and dp[i-2] are already filled. ✓

Worked Example 1: Climbing Stairs

STATE:    dp[i] = number of distinct ways to reach step i
RECUR:    dp[i] = dp[i-1] + dp[i-2]
BASE:     dp[0] = 1, dp[1] = 1
FILL:     left to right (i = 2 to n)
ANSWER:   dp[n]

Table for n=6:
i:    0  1  2  3  4   5   6
dp:   1  1  2  3  5   8  13

dp[2] = dp[1]+dp[0] = 1+1 = 2
dp[3] = dp[2]+dp[1] = 2+1 = 3
dp[4] = dp[3]+dp[2] = 3+2 = 5
dp[5] = dp[4]+dp[3] = 5+3 = 8
dp[6] = dp[5]+dp[4] = 8+5 = 13

Ways to climb 6 stairs = 13 ✓

Worked Example 2: Unique Paths (2D Table)

STATE:    dp[i][j] = number of paths to cell (i,j)
RECUR:    dp[i][j] = dp[i-1][j] + dp[i][j-1]
BASE:     dp[0][j] = 1 for all j (first row: only rightward moves)
          dp[i][0] = 1 for all i (first col: only downward moves)
FILL:     row by row, left to right (i=1..m-1, j=1..n-1)
ANSWER:   dp[m-1][n-1]

Table for 4×4 grid:
      j=0  j=1  j=2  j=3
i=0 [  1,   1,   1,   1 ]  ← first row all 1
i=1 [  1,   2,   3,   4 ]
i=2 [  1,   3,   6,  10 ]
i=3 [  1,   4,  10,  20 ]

dp[1][1] = dp[0][1]+dp[1][0] = 1+1 = 2
dp[1][2] = dp[0][2]+dp[1][1] = 1+2 = 3
dp[2][2] = dp[1][2]+dp[2][1] = 3+3 = 6
dp[3][3] = dp[2][3]+dp[3][2] = 10+10 = 20

Paths in 4×4 grid = 20 ✓

Worked Example 3: 0/1 Knapsack

STATE:    dp[i][w] = max value using items 0..i-1 with capacity w
RECUR:    dp[i][w] = max(
            dp[i-1][w],                      ← skip item i
            values[i-1] + dp[i-1][w-weights[i-1]]  ← take item i
          )
          (take only if weights[i-1] <= w)
BASE:     dp[0][w] = 0 for all w (no items → no value)
          dp[i][0] = 0 for all i (no capacity → no value)
FILL:     i=1..n, w=1..W (row by row)
ANSWER:   dp[n][W]

items = [(weight=2,val=3),(weight=3,val=4),(weight=4,val=5),(weight=5,val=6)]
W=5, n=4

Table dp[i][w]:
      w=0  w=1  w=2  w=3  w=4  w=5
i=0 [  0,   0,   0,   0,   0,   0 ]  ← base: no items
i=1 [  0,   0,   3,   3,   3,   3 ]  ← item1: w=2,v=3
i=2 [  0,   0,   3,   4,   4,   7 ]  ← item2: w=3,v=4
i=3 [  0,   0,   3,   4,   5,   7 ]  ← item3: w=4,v=5
i=4 [  0,   0,   3,   4,   5,   7 ]  ← item4: w=5,v=6

dp[2][5] = max(dp[1][5], 4+dp[1][5-3]) = max(3, 4+3) = 7  ← take both
dp[4][W=5] = 7 ✓ (items with w=2,v=3 + w=3,v=4 = w=5, v=7)

Complete Tabulation Implementations

Output:
fib(10):            55
climbStairs(6):     13
uniquePaths(4,4):   20
coinChange([1,3,4]): 2
knapsack(W=5):       7
LCS(abcde,ace):      3

Space Optimisation

Tabulation's key advantage: you can reduce space once you identify which table cells are still needed.

1D Space Reduction: Rolling Variables

WHEN: dp[i] depends only on the last k values.

Fibonacci: dp[i] = dp[i-1] + dp[i-2]
  Only last 2 values needed. Use two variables.

BEFORE (O(n) space):              AFTER (O(1) space):
  dp = [0]*(n+1)                    prev2, prev1 = 0, 1
  dp[0]=0; dp[1]=1                  for i in range(2, n+1):
  for i in range(2,n+1):                prev2, prev1 = prev1, prev1+prev2
    dp[i] = dp[i-1]+dp[i-2]         return prev1
  return dp[n]

2D Space Reduction: Rolling Row

WHEN: dp[i][j] depends only on the current row and the PREVIOUS row.

Unique Paths: dp[i][j] = dp[i-1][j] + dp[i][j-1]
  Only need previous row and current row being built.

BEFORE (O(m*n)):                  AFTER (O(n)):
  dp[m][n]                          prev = [1]*n   ← row i-1
  fill all rows                     for i in range(1,m):
  return dp[m-1][n-1]                   curr = [1]*n   ← row i
                                        for j in range(1,n):
                                            curr[j]=prev[j]+curr[j-1]
                                        prev = curr
                                    return prev[n-1]

LCS: dp[i][j] = dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
  Needs dp[i-1] (previous row) and dp[i][j-1] (current row, previous col).
  O(m*n) → O(n) with single rolling row.

0/1 Knapsack: O(W) Space

INSIGHT: dp[i][w] = dp[i-1][w] or dp[i-1][w-weight[i]] + value[i]
  Only needs the PREVIOUS row dp[i-1].
  Can use a single 1D array if we iterate w from W DOWN TO 0.

WHY RIGHT TO LEFT?
  When updating dp[w], we need dp[w - weight[i]] (smaller index).
  If we go left to right, dp[w-weight] is already UPDATED for item i.
  → We'd be using item i TWICE (unbounded knapsack behaviour).
  Going right to left: dp[w-weight] hasn't been updated yet → still row i-1.
  → Correct 0/1 knapsack (use each item at most once).

BEFORE (O(n*W)):                  AFTER (O(W)):
  dp[n+1][W+1] 2D table            dp = [0]*(W+1)
                                    for i in range(n):
  for i in range(1,n+1):               for w in range(W, weights[i]-1, -1):
    for w in range(W+1):                   dp[w] = max(dp[w],
      dp[i][w]=dp[i-1][w]                             values[i]+dp[w-weights[i]])
      if weights[i-1]<=w:          return dp[W]
        dp[i][w]=max(...)
  return dp[n][W]

Output (space-optimised):
fib(10):           55
uniquePaths(4,4):  20
LCS(abcde,ace):    3
knapsack(W=5):     7

Fill Order Reference

RECURRENCE               FILL ORDER                   WHY
──────────────────────────────────────────────────────────────────────
dp[i]=f(dp[i-1])         i: 0 → n                     need i-1 before i
dp[i]=f(dp[i-1],dp[i-2]) i: 0 → n                     need i-1,i-2 before i
dp[i][j]=f(dp[i-1][j],   i: 0→m, j: 0→n (row by row) need row above and
          dp[i][j-1])                                   left in same row
dp[i][j]=f(dp[i][j+1],   i: m→0 (reverse), j: n→0     need row below and
          dp[i+1][j])                                   right (reverse fill)
dp[i][j]=f(dp[i][k],     i: length ascending,          need smaller
          dp[k+1][j])     j = i+len for each len        intervals first
          all k in [i,j]  (interval DP)
dp[i][j]=f(dp[i-1][j-1], i: 0→m, j: 0→n               need diagonal above-left
          dp[i-1][j],                                   and adjacent cells
          dp[i][j-1])

Complexity Summary

Common Mistakes

Wrong fill order — reading an uninitialised cell. For dp[i][j] = dp[i-1][j] + dp[i][j-1], if you fill column by column (j outer, i inner), then dp[i][j-1] refers to column j-1 which was fully computed — correct. But dp[i-1][j] refers to the previous row in the current column, already computed — also correct. Either row-first or column-first works for this recurrence. But for LCS where dp[i][j] needs the diagonal dp[i-1][j-1], any row-major fill is correct. Always trace dependencies before choosing loop order.

Knapsack: iterating w left to right in the 1D optimised version. The 1D 0/1 Knapsack MUST iterate w from W down to weights[i]. Left-to-right updates dp[w-weight] before dp[w] reads it, effectively using item i twice. Right-to-left reads dp[w-weight] from the previous item's row state. This is the single most common knapsack implementation bug.

Forgetting to initialise base cases explicitly. Languages like Java and C++ zero-initialise int arrays, so dp[0][w] = 0 is automatic. Python creates lists explicitly. JavaScript's new Array(n).fill(0) is needed. But for non-zero base cases (e.g., first row of Unique Paths should be all 1s), explicit initialisation is always required — never assume default values are correct.

Off-by-one: table size vs last index. LCS of strings of length m and n uses a table of size (m+1) × (n+1), indexed dp[0..m][0..n]. The +1 accommodates the empty string base case at index 0. Using dp[m][n] as table size (without +1) causes out-of-bounds when accessing dp[m][n]. Always allocate n+1 when the state range is 0..n.

Using sentinel INT_MAX then adding 1. For minimum problems, dp = [INT_MAX] * (amount+1) followed by dp[i] = min(dp[i], 1 + dp[i-coin]) overflows if dp[i-coin] == INT_MAX. Use amount+1 as sentinel instead — it can't be a valid answer (minimum coins for amount is at most amount, using all 1s), and 1 + (amount+1) = amount+2 still compares correctly without overflow.

Interview Questions

Q: How do you determine the fill order for a 2D DP table?

Trace the dependencies of dp[i][j]. If it needs dp[i-1][j] (above) and dp[i][j-1] (left), fill row by row left to right — ensuring both are already filled. If it needs dp[i+1][j] (below) or dp[i][j+1] (right), reverse the fill direction. For interval DP where dp[i][j] needs dp[i][k] and dp[k+1][j] (sub-intervals), fill by increasing interval length. The rule: dependencies must always be filled before the dependent.

Q: Why does 1D Knapsack optimisation require iterating W downward?

The 2D recurrence is dp[i][w] = max(dp[i-1][w], values[i] + dp[i-1][w-wt]) — both references are from row i-1. In the 1D version, dp[w] represents the previous row before being updated. If we iterate w from small to large, dp[w-wt] is updated before dp[w] reads it — meaning item i was already "used" at capacity w-wt. Iterating from W down to wt ensures dp[w-wt] still holds the i-1 row value when we read it.

Q: What is the space complexity of tabulated LCS after space optimisation?

Full 2D LCS uses O(m×n). Since dp[i][j] only depends on dp[i-1][j] (above), dp[i][j-1] (current row, left), and dp[i-1][j-1] (diagonal above-left), computing row i only needs row i-1. Use two 1D arrays (prev and curr) of size n+1 — O(n) space. If m < n, swap the strings to use O(min(m,n)) space.

Summary

Tabulation is bottom-up DP: fill a table iteratively from base cases toward the answer, with no recursion.

The four-step structure:

1. ›Declare the table with the right dimensions and sentinel
2. ›Fill base cases explicitly before loops
3. ›Fill remaining cells in dependency order (small → large)
4. ›Return the final cell

Conversion from memoization:

• ›Recursive calls → direct table lookups
• ›Cache check → removed (loop order guarantees freshness)
• ›Base cases inside function → explicit table initialisation before loops

Space optimisation patterns:

• ›1D problems depending on last k values → k rolling variables
• ›2D problems depending only on previous row → two 1D arrays
• ›0/1 Knapsack → single 1D array, iterate W downward to 0

Fill order reference:

• ›dp[i] needs dp[i-1] → fill left to right
• ›dp[i][j] needs dp[i-1][j] and dp[i][j-1] → row by row, left to right
• ›Interval DP dp[i][j] needs sub-intervals → fill by increasing length

In the next topic you will explore Memoization vs Tabulation — a direct comparison of when each approach is faster, which handles sparse sub-problems better, and how to choose between them.