Dynamic Programming — Memoization & Tabulation Explained

Dynamic programming is a way to solve problems by saving answers to smaller subproblems and reusing them later. It helps when the same subproblems show up again and the full answer can be built from those smaller answers.

The two main styles are memoization and tabulation. Memoization stores answers during a recursive solution. Tabulation fills answers in a bottom-up order, usually with an array or table.

When dynamic programming works

Dynamic programming is useful when two conditions hold.

First, subproblems overlap. That means the same intermediate result is needed more than once. Second, larger answers can be built from smaller answers in a consistent way.

If those conditions do not hold, storing old results may add memory cost without helping much.

Memoization vs. tabulation

Memoization: top-down storage

Memoization starts with the recursive idea. When the algorithm solves a subproblem for the first time, it stores the result. Later calls reuse the stored value instead of recomputing it.

This style is often easier when the recurrence is clear but the order of all needed states is not.

Tabulation: bottom-up build

Tabulation starts from the base cases and fills states in an order that makes dependencies available when needed.

This style is often easier when you already know a clean iteration order and want explicit control over the table.

Dynamic programming example: Fibonacci

The Fibonacci sequence is defined by

$$F(0) = 0, \quad F(1) = 1$$

and, for $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

A plain recursive solution repeats work. For example, computing $F(5)$ needs $F(4)$ and $F(3)$, and then computing $F(4)$ needs $F(3)$ again. That repeated $F(3)$ call is the kind of waste dynamic programming removes.

Memoization on Fibonacci

With memoization, the recurrence stays the same, but each value is stored after the first time it is computed.

For $F(5)$, the useful sequence is:

• compute and store $F(0)=0$
• compute and store $F(1)=1$
• compute and store $F(2)=1$
• compute and store $F(3)=2$
• compute and store $F(4)=3$
• compute and store $F(5)=5$

The key point is that each state is computed once. Later requests read the stored value.

Tabulation on Fibonacci

With tabulation, you build from the base cases upward:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

This version makes the dependency order obvious: each new value uses entries that are already known.

Why dynamic programming can be faster

If a problem has only $k$ distinct states that matter, dynamic programming tries to solve those $k$ states once each. That can turn a large recursive tree into a much smaller computation.

The exact speedup depends on the problem. Dynamic programming is not automatically fast. It helps when repeated work is a real part of the original solution.

Common mistakes in dynamic programming

Using it when subproblems do not overlap

Not every recursive problem is a dynamic programming problem. If almost every subproblem is different, caching results may not save enough work to matter.

Defining the wrong state

The state has to include all the information needed for the next step. If important information is missing, the recurrence can look valid but produce wrong answers.

Getting the base cases wrong

Base cases anchor the whole method. If the starting values are wrong, every later state built from them is wrong too.

Filling the table in the wrong order

Tabulation only works when each state is filled after the states it depends on. A correct recurrence can still fail if the fill order is wrong.

Assuming dynamic programming always means optimization

Many famous examples maximize or minimize something, but dynamic programming is also used for counting and decision problems. The real signal is reusable subproblems, not the word "best."

Where dynamic programming is used

Dynamic programming appears in problems such as edit distance, longest common subsequence, counting paths, knapsack-style optimization, and some shortest-path settings.

When you are deciding whether to try it, ask two questions:

• do the smaller subproblems repeat?
• can the larger answer be built from those smaller answers?

If both answers are yes, dynamic programming is a strong candidate.

Try a similar problem

Try your own version with the number of ways to climb $n$ steps if each move is either $1$ step or $2$ steps. The recurrence is simple, the repeated subproblems are easy to spot, and it is a good next example after Fibonacci.