Dynamic Programming: Complete Guide to Memoization

Coding Patterns - Guide to 30 Core Algorithm Patterns

Dynamic programming is the difference between a solution that times out and one that runs in milliseconds. A naive recursion recomputes the same subproblems over and over, which costs

O(2^N)

work in the worst case. A DP solution computes each subproblem once, caches the answer, and drops the total to

O(N)

. This is the pattern behind counting questions, path questions, and most of the “minimum cost with a constraint” problems that show up in interviews.

Definition: dynamic programming is an approach where you define the smallest unit of state, compute the answer for every reachable state in dependency order, and store each answer so later states read it instead of recomputing it.

Real-World Analogy

Picture a hiker crossing a ridge where several trails join at the same junctions before the summit. A hiker without a notebook walks every trail in full and crosses the same junction three times, paying the same climb each time. A hiker with a notebook writes the junction’s height and distance on the first visit. Every later route reads the notebook instead of re-walking the approach. The saved numbers stay valid because the terrain does not change between routes.

Each junction is a subproblem and the notebook is the memo table. What the hiker records at each junction is the state. When you define a DP state, you are deciding which information makes a subproblem self-contained. Once the hiker is standing at a junction, the route that brought them there no longer matters for the rest of the climb.

Visual Explanation

Fibonacci is the smallest example that shows the pattern. fib(5) splits into fib(4) and fib(3), and each of those splits again. The same values keep reappearing in different branches.

    graph TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4 --> F3b["fib(3)"]
    F4 --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    F2a --> F1c["fib(1)"]
    F2a --> F0a["fib(0)"]
    F2b --> F1d["fib(1)"]
    F2b --> F0b["fib(0)"]
    F2c --> F1e["fib(1)"]
    F2c --> F0c["fib(0)"]

fib(3) appears twice and fib(2) three times. Each extra level of n doubles the waste, which is where the

O(2^N)

bound comes from. DP fixes this by computing each value once and storing it. There are two ways to arrange that, and both produce the same table of answers.

Top-down (memoization) keeps the recursion and adds a cache. Before computing a state you check the cache, and after computing it you store the result. This is the easier style to write because it follows the recurrence directly.

Bottom-up (tabulation) drops the recursion and fills the table from the smallest state upward. Every dependency is ready by the time a state is computed, because it was filled earlier in the loop. This style also wins on space, since you can often keep two variables instead of the whole table.

    graph LR
    A["Recurrence: f(n) = f(n-1) + f(n-2)"] --> B["Top-down: solve f(n), cache every result"]
    A --> C["Bottom-up: fill f(0), f(1), up to f(n)"]

When to Use This Pattern

These characteristics point to DP rather than another pattern.

The problem asks how many ways something can happen, like counting decodings or distinct subsequences. Counting cannot be shortcut by a local rule, so overlapping states are nearly guaranteed.
The problem asks for a minimum or maximum and each choice restricts later choices. House Robber is the cleanest example, because robbing one house forbids the next one.
The brute force or naive recursion recomputes the same sub-input in different branches. Trace two branches by hand and look for the same call appearing twice.
The input is two strings and the problem asks about a common subsequence or the edits needed to turn one string into the other. Those problems are 2D tables in practice.
A greedy choice fails. If taking the locally best option now can block a better global option later, DP is the fallback.

Complexity Analysis

DP complexity follows one rule: time is the number of states times the cost of a transition, and space is the size of the cache.

Approach	Time	Space	Notes
Naive recursion	O(2^N)	O(N)	the recursion tree re-expands every subtree
Memoization	O(N)	O(N)	one solve per state, one cache entry per state
Tabulation	O(N)	O(N)	each state filled once in dependency order
2D table	O(N^2)	O(N^2)	every pair of inputs becomes one cell
Space-optimized	O(N)	O(1)	keep only the states the next step reads

The memoization time bound assumes each transition does constant work. Look-back patterns like longest increasing subsequence break that assumption, because every state scans all earlier states and the cost becomes

O(N^2)

. When an interviewer asks about space, they usually want the optimized version that keeps two variables, which is why the space-optimized row exists.

Memorizing complexity tradeoffs is half the battle. The other half is remembering them under pressure. Review this pattern with spaced repetition so the analysis becomes automatic by interview day.

Common Mistakes

These errors all share a root cause: the recurrence is correct on paper but the state around it is wrong.

Defining the wrong state. The state is the set of variables that fully describes a subproblem. Newcomers often track only the current index when the answer also depends on something else, like the previous character chosen or the remaining budget. The recurrence then reads the wrong value and the answer is subtly off. To catch it during practice, write the recurrence in words before writing code. If the words need a fact that is not in the state, the state is missing a variable.

Getting base cases wrong for the empty input. Counting problems initialize the empty case to 1, because there is exactly one way to do nothing. Minimum problems initialize it to 0, because nothing costs nothing. Mixing the two produces answers that are off by a constant, and the tests usually fail on the smallest input first. Practice with n = 0 and n = 1 before anything else.

Filling the table in the wrong order. In a 2D table like longest common subsequence, each cell reads the row above and the column to the left, so filling row by row keeps those values final. In the space-optimized 1D versions, the new value overwrites the old one, and a transition that reads the overwritten slot sees the wrong number. Write down which states each transition reads, then order the loop so those states are settled first.

Using DP when greedy is enough. Some problems look like DP but a local rule settles them. If the optimal answer can be built by always taking the locally best choice and that choice never needs to be undone, greedy is correct and faster to write. Ask one question before reaching for a table: does the locally best choice ever need to be undone? If it does not, greedy.

These mistakes are expensive because they look correct until they fail on a hidden test case. Our review decks flag exactly these edge cases and drill them until they are reflex. Add this pattern to your queue .

Related Patterns

Recursion . Every top-down DP is a recursive function with a cache added. The recursion page covers the function structure, and DP adds the storage that stops the re-expansion.
Divide and Conquer . Both patterns split problems into smaller pieces. Divide and conquer assumes the pieces are independent, while DP assumes they overlap. Same skeleton, opposite assumptions.
Greedy Algorithms . Greedy is what you try before DP. If a locally optimal choice locks in the global optimum, no table is needed.

Next Steps

Once you can define a state without second-guessing yourself, the code becomes mechanical. The code templates page has the memoization and tabulation blueprints in 6 languages, and the practice problems page works through six interview problems from Easy to Hard.

Reading about a pattern once is not enough to own it in an interview. Practice this pattern with spaced repetition and turn recognition into recall.