Dynamic Programming — Memoization & Tabulation Explained

When you write dynamic programming, the big decision is usually just one fork: memoization or tabulation. Both solve the same problem by reusing answers to smaller subproblems; they only differ in direction. Memoization stores answers during a recursive solution. Tabulation fills answers in a bottom-up order, usually with an array or table.

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.

Memoization vs. Tabulation Side By Side

Memoization starts with the recursive idea. When the algorithm solves a subproblem for the first time, it stores the result, and 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 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.

When To Use Dynamic Programming At All

Before choosing either style, check that dynamic programming even fits. Two conditions must hold.

First, subproblems overlap, meaning 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.

Applying Both Styles: Fibonacci

The Fibonacci sequence is defined by

and, for $n \ge 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:

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

Why Either Style 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.

Which Mistakes Trip Each Approach

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

This one is specific to tabulation: it 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 whether the smaller subproblems repeat and whether the larger answer can be built from them. If both answers are yes, it is a strong candidate.

A clean next exercise is counting the number of ways to climb $n$ steps if each move is either $1$ step or $2$ steps. The recurrence mirrors Fibonacci, and you can solve it once with memoization and once with tabulation to feel the difference between the two styles.