Coding Interview: Patterns & DSA · Recursion, Backtracking & DP · Lesson 3 of 3
Tabulation & classic DP
Tabulation is bottom-up DP: instead of recursing, you fill a table from the smallest subproblems up to the answer. It removes recursion overhead and makes the space optimization obvious — often you only need the last row or two.
def climb_stairs(n): # ways to reach step n taking 1 or 2 steps if n < 2: return 1 a, b = 1, 1 # ways to reach step 0 and step 1 for _ in range(2, n + 1): a, b = b, a + b # only the last two states matter return b # O(n) time, O(1) space
- Memoization vs tabulation: same subproblems and complexity; top-down is easier to write, bottom-up avoids stack limits and enables rolling-array space savings.
- 0/1 knapsack: a 2-D table over (item, remaining capacity) — the template for many 'pick a subset under a budget' problems.
- Longest common subsequence / edit distance: a 2-D table over prefixes of the two strings.
- Coin change:
dp[amount]= fewest coins to make each amount, built up from 0.
Rolling arrayWhen
dp[i] depends only on dp[i-1] (and maybe dp[i-2]), you do not need the whole table — keep the last one or two values and drop O(n) space to O(1). Climbing stairs above does exactly this.State the recurrenceThe heart of any DP answer is one sentence: '
dp[i] means X, and dp[i] = f(dp[smaller]).' Say the state definition and the transition out loud before coding — that is what interviewers grade.◆ Lock it in
- Tabulation fills a table bottom-up; same complexity as memoization, no recursion.
- A rolling array drops space to
O(1)when only the last rows matter. - Classics: knapsack, LCS, edit distance, coin change — all a state + transition.
Feynman drill — say it out loudState the DP recurrence for climbing stairs and explain the rolling-array space optimization.
Step 1 rate your confidence · Step 2 pick your answer
The main practical advantage of tabulation (bottom-up) over memoization (top-down) is:
Step 1 — how sure are you?