Memoization and tabulation - DSA Learning Guide

Overview

Dynamic programming (DP) solves problems whose answers are built from answers to smaller overlapping subproblems. Instead of recomputing the same subproblem many times, DP stores each result once and reuses it.

Memoization is top-down: write the natural recursion and cache results. Tabulation is bottom-up: fill a table from the smallest subproblems upward. Both give the same complexity; the choice is about clarity, stack depth, and memory optimization.

Writing answers in the margin

If a teacher asks for 7 x 8 twenty times, you calculate it once and write 56 in the margin. Memoization is checking the margin before calculating; tabulation is filling the whole multiplication table in order beforehand.

When to use it

The problem asks for a count of ways, a minimum or maximum cost, or whether something is possible.
A brute-force recursion calls itself with the same arguments repeatedly (overlapping subproblems).
An optimal answer can be built from optimal answers to smaller inputs (optimal substructure).

Problem patterns it solves

Linear recurrence

Recognize it when: answer for n depends on the previous one or two answers.

70. Climbing Stairs
509. Fibonacci Number
1137. N-th Tribonacci Number
746. Min Cost Climbing Stairs

Take or skip

Recognize it when: each item is either chosen or not, with a rule such as no two adjacent or a capacity.

198. House Robber
740. Delete and Earn
416. Partition Equal Subset Sum

Unbounded choices

Recognize it when: items can be reused any number of times: coins, squares, steps.

322. Coin Change
518. Coin Change II
279. Perfect Squares
377. Combination Sum IV

Two sequences

Recognize it when: compare two strings or arrays; state is (i, j).

1143. Longest Common Subsequence
72. Edit Distance

Grid paths

Recognize it when: move right or down, count paths or minimize cost.

62. Unique Paths
64. Minimum Path Sum

Where it is used in real software

Spell check and autocorrect

Edit distance DP measures how many keystrokes separate a typo from dictionary words.

diff and git

Line-based diff tools compute a longest common subsequence of lines to show the smallest set of changes.

Bioinformatics

DNA and protein alignment (Needleman-Wunsch, Smith-Waterman) are 2D DP tables over two sequences.

UI frameworks

React useMemo and selector libraries such as Reselect memoize expensive calculations by their inputs, the same idea as top-down DP.

Key terms

State: The parameters that uniquely identify a subproblem, such as dp[i] or dp[i][j].
Transition: The formula that computes a state from smaller states.
Base case: The smallest states whose answers are known directly.
Overlapping subproblems: The same state is needed by many larger states.

How it works, step by step

1
Define the state in words
Example: ways(n) = number of distinct ways to climb n stairs taking 1 or 2 steps at a time.
2
Write the transition
The last move was 1 step or 2 steps, so ways(n) = ways(n - 1) + ways(n - 2).
3
Set base cases
ways(0) = 1 (the empty climb) and ways(1) = 1.
4
Choose an evaluation order
Memoization lets recursion decide the order. Tabulation iterates so every dependency is computed before it is used.
5
Optimize space
If a state only depends on the previous few states, keep just those variables instead of the whole table.

Fill dp[] for climbing stairs, n = 6

STEP 1Base cases: dp[0] = 1 (the empty climb) and dp[1] = 1.

Climbing stairs with n = 6

ways(n) = ways(n - 1) + ways(n - 2), ways(0) = 1, ways(1) = 1

n	0	1	2	3	4	5	6
ways(n)	1	1	2	3	5	8	13

NOWn: ways(n) | 0: 1 | 1: 1 | 2: 2 | 3: 3 | 4: 5 | 5: 8 | 6: 13

There are 13 ways to climb 6 stairs. Plain recursion makes 25 calls for n = 6 and grows exponentially; the table computes each value once for 7 total states.

Implementation

1function climbStairs(n: number, memo = new Map<number, number>()): number {2  if (n <= 1) return 1;                 // base cases3  if (memo.has(n)) return memo.get(n)!; // reuse stored answer4 5  const result = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);6  memo.set(n, result);7  return result;8}

Complexity and performance

Naive recursionO(2^n)

Each call branches twice and repeats work.

Memo / table timeO(n)

Number of states times work per transition.

Table spaceO(n)

One slot per state; recursion also uses O(n) stack.

Optimized spaceO(1)

Keep only the states the transition reads.

Trade-offs

Memoization

Easy to derive from recursion and only computes states that are actually reached. Risks stack overflow for deep inputs and has hashing overhead.

Tabulation

No recursion, predictable memory access, and easy space optimization. Requires you to know a valid order and may compute unneeded states.

Variants and related techniques

2D DP

State depends on two indexes, such as positions in two strings (LCS, edit distance) or grid coordinates.

Knapsack

dp[i][capacity] chooses to take or skip each item; iterate capacity backward to use a 1D array for 0/1 knapsack.

State-machine DP

Add a mode to the state, for example holding or not holding stock, to model rules like cooldowns.

Common mistakes

Defining a vague state.
Fix: Write it as a sentence: dp[i] = the answer for the first i items under rule X.
Wrong base cases.
Fix: Check the smallest inputs by hand; empty inputs often have answer 1 for counting and 0 for costs.
Iterating in an order that reads uncomputed states.
Fix: Every state on the right side of the transition must already be filled.

Interview questions

How do you recognize a DP problem?

Look for choices at each step, an optimization or counting goal, and a brute-force recursion that revisits the same arguments.

How do you compute DP complexity?

Number of distinct states multiplied by the work per state transition.

Memoization or tabulation in an interview?

Start with memoized recursion because it is fastest to derive correctly, then convert to tabulation if stack depth or space optimization matters.

Practice problems

Problem	Difficulty	What it trains
Climbing Stairs	Easy	First recurrence.
Min Cost Climbing Stairs	Easy	Minimum instead of count.
House Robber	Medium	Take or skip decisions.
Coin Change	Medium	Unbounded choices.
Unique Paths	Medium	2D grid DP.
Longest Common Subsequence	Medium	Two-string state.
Edit Distance	Hard	Three transitions per state.