DP Fundamentals: Memo & Table

A recursive Fibonacci of five lines takes minutes for n = 50; add one array and it answers instantly. That one trick, remembering answers to subproblems, is dynamic programming, and it solves a huge share of interview and contest problems.

intermediate⏱ 14 min read

←Builds on

4Generating Subsets & PermutationsDP is complete search plus memory.0Recursion & the Call StackMemoization is a recursive function that writes its answers down.6Cycles, Topological Sort, Bipartite CheckDP states form a DAG, and a table must be filled in topological order.

Leads to→

101-D DP: Coins & LIS1-D DP is the table form of a memo with one index, filled left to right.10Floyd–Warshall: DP on GraphsThe state is "shortest path using only the first k vertices", a textbook DP.10DP on TreesTree DP is the same memo idea with one state per vertex.10Bitmask DPMemoising over subsets turns n! tours into 2ⁿ·n states.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01The same question, asked again and again

Write Fibonacci the obvious way: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0, fib(1) = 1. It is correct, and it is painfully slow.

Draw the calls for fib(5) and the reason jumps out: fib(3) is computed twice, fib(2) three times, and every repeat drags its whole subtree along. The number of calls grows like φⁿ ≈ 1.6ⁿ, so fib(50) makes tens of billions of calls.

Yet there are only n + 1 different questions: fib(0), fib(1), …, fib(n). The recursion is not doing hard work, it is doing the same work over and over. This is called overlapping subproblems, and it is the first signal that dynamic programming (DP) will help.

Coloured vertices are repeats: the same subproblem solved from scratch again.

02Two ways to remember: memo and table

Top-down (memoization). Keep the recursion, add a cache. Before computing fib(k), look in memo[k]; if it is there, return it. Otherwise compute, store, return. Each subproblem is solved once, so fib(5) makes 9 calls instead of 15, and fib(50) makes 99 instead of billions.

Bottom-up (tabulation). Drop the recursion. Fill an array from the smallest subproblem upwards: f[0] = 0, f[1] = 1, then f[i] = f[i-1] + f[i-2] for i = 2..n. No call stack, no cache lookups, just a loop.

Both give O(n) time. Memoization is the easier first step (you only add a cache to working code) and computes only the states it actually needs. Tabulation is faster in practice, cannot overflow the stack, and often lets you keep only the last row, here just two variables.

03When DP works: two properties

DP applies when a problem has both:

Overlapping subproblems: the recursion keeps meeting the same smaller questions. (Merge sort splits into *different* halves, so caching would not help it.)
Optimal substructure: the best answer to the big problem is built from best answers to smaller ones. A shortest path from A to C through B contains a shortest path from A to B.

A useful picture: draw every subproblem as a vertex and draw an edge u → v when v needs the answer of u. For Fibonacci you get 6 vertices in a line with jumps of one and two, not a tree of 15 calls. This graph never has a cycle (a subproblem cannot depend on itself), so it is a DAG, and solving the subproblems in topological order is exactly what the bottom-up loop does.

04Every DP is a shortest path on a DAG

Take that picture seriously. In a weighted DAG, the shortest distance to a vertex is

dist[v] = min over edges u → v of dist[u] + w(u, v)

and you can compute it in one pass by visiting vertices in topological order: by the time you reach v, every u that points to v is final. No priority queue, no repeated relaxation, just O(V + E).

Now read any DP recurrence in that language. The states are vertices, the choices are edges, the cost of a choice is the edge weight, min or max picks the best incoming edge, and the base case is the source. Coin change, knapsack, LCS and grid paths in the next lessons are all this one idea with a different graph. When you design a DP, ask: what are my vertices, and in what order can I finish them?

Processed left to right, each vertex looks only at its incoming edges.

05From backtracking to DP: the recipe

In Complete Search you wrote recursive functions that try every choice. DP is often just that code plus a memo. If the recursive function’s result depends only on its arguments (not on global state you mutate along the way), those arguments are a state, and you can cache by state.

The recipe:

State: what does dp[...] mean, in one sentence? (fib(i) = the i-th Fibonacci number.)
Recurrence: how is a state built from smaller ones?
Base cases: the states you know without thinking.
Order: fill so that dependencies come first, or let memoized recursion handle it.
Answer: which state, or which min/max over states, is the final result?

Cost = (number of states) × (work per state). Most DP bugs are a fuzzy state definition, so write that sentence first.

Cost at a glance

Naive recursive fib(n)O(φⁿ)

Memoized or tabulated fib(n)O(n)

Memory, keeping only the last two valuesO(1)

Any DPstates × work per state

Remember

DP pays off when subproblems overlap and the optimal answer is built from optimal answers to subproblems.
Memoization adds a cache to recursion; tabulation fills a table bottom-up in dependency order; both cost states × work per state.
Think of states as vertices of a DAG: a DP recurrence is a shortest (or longest) path computed in topological order.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the call counter: the naive tree makes 15 calls, the memoized run skips whole dimmed subtrees, then the table fills in 4 additions. Try n = 7.

Interactive visualizerfocus here, then space ← →

Naive recursion: fib(5) · calls: 1

Call fib(5). (call #1)

Pseudocode

 1 fib(n): if n < 2 return n 2 naive:  return fib(n-1) + fib(n-2)   // recomputes subproblems 3 memoized: if cached return it; else compute, cache, return 4 tabulation: table[0]=0, table[1]=1, 5   table[i] = table[i-1] + table[i-2]   // bottom-up

1 / 1

Check

Three questions. Pick an answer to see why.

With memoization, how many times is the body of fib(k) actually computed (not just looked up) while evaluating fib(30)?

Which problem does NOT benefit from memoization?

A DP has states dp[i][j] for 0 ≤ i, j ≤ n, and each state takes a min over n options. What is the running time?

Practice

Real problems to lock it in, easiest first.

LeetCodeFibonacci Number beginner↗LeetCodeClimbing Stairs beginner↗CSESDice Combinations intermediate↗LeetCodeHouse Robber intermediate↗CSESRemoving Digits intermediate↗