About 25 percent of the algorithm questions on a typical interview list are dynamic programming problems. About 5 percent of the engineers I have worked with describe themselves as comfortable with DP. The gap is not because DP is hard. The gap is because DP is taught backwards. People are shown the finished dp[i] = something(dp[i-1]) recurrence and asked to derive insight from it, when the actual skill is the process that produces the recurrence. Reverse the order, walk through the framework, and DP stops being magic almost immediately.

The argument I want to make is that DP is pattern matching. Not invention, not creativity, not deep mathematical insight. There are about six recurring patterns, a five-step framework that maps any new problem onto one of them, and two implementation styles that trade memory for clarity. Once you internalize the framework, the recurrence is what falls out at the end, not what you start with.

What DP actually is

Dynamic programming is the technique of solving a problem by combining solutions to overlapping subproblems. Two conditions have to hold for DP to apply, and if either one is missing you should reach for something else.

1. Optimal substructure. The optimal solution to the problem contains optimal solutions to subproblems. The shortest path from A to C through B is the shortest path from A to B plus the shortest path from B to C. Greedy algorithms also exploit optimal substructure, so this alone is not what makes a problem DP-shaped.
2. Overlapping subproblems. The same subproblem comes up multiple times during the recursive decomposition. This is what separates DP from divide-and-conquer. Merge sort recursively splits in half, but the two halves are different subproblems, so caching does not help. Fibonacci computed naively recomputes fib(3) again and again, so caching is the entire game.

If both conditions hold, DP is the right tool. The question becomes: what is the subproblem, what is the recurrence between subproblems, and how do you store the answers efficiently?

The five-step framework

This is the procedure I follow on every DP problem I have not seen before. It is mechanical, and that is the point. The mechanical version gets to the right answer; the "intuition" version gets stuck.

Step 1: Define the state. What information uniquely identifies a subproblem? "The minimum cost to reach cell (r, c)" is a state. "The longest increasing subsequence ending at index i" is a state. "The maximum profit using at most k transactions ending on day i while holding/not holding a stock" is a state with three dimensions. The state is the set of variables you would need to memoize.

Step 2: Define the recurrence. Given a state, how is its answer computed from the answers of strictly smaller states? This is the line that ends up looking like dp[i] = min(dp[i-1], dp[i-2] + cost[i]). You derive it by asking: at this state, what choices do I have, and what does each choice cost?

Step 3: Identify base cases. What states have answers that are known directly, without recursion? Usually the smallest input (dp[0] = 0) or an empty subproblem (dp[""] = 0).

Step 4: Decide on order of computation. Top-down (memoized recursion) computes states only when needed; bottom-up (tabulation) fills in a table from smallest to largest. The two approaches give the same answer but have different tradeoffs (covered below).

Step 5: Optimize space if you can. Many DPs only need the previous row or two of the table. If your recurrence is dp[i] = f(dp[i-1], dp[i-2]), you can drop the full array and keep two variables. This is where the textbook O(n) DP becomes O(1) space.

A worked walkthrough: climbing stairs

The canonical first DP problem. You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of n stairs?

Step 1 (state): Let dp[i] be the number of ways to reach step i. The state has one dimension: the current step.

Step 2 (recurrence): To get to step i, your last move was either a 1-step from i-1 or a 2-step from i-2. So dp[i] = dp[i-1] + dp[i-2]. (This is just Fibonacci, which is a fact about the problem, not about the framework.)

Step 3 (base cases): dp[0] = 1 (one way to be at the start: stay put). dp[1] = 1 (one way to reach step 1: take a single step).

Step 4 (order): Bottom-up is cleaner here because the recurrence is linear and the dependency direction is obvious.

Step 5 (space): We only need the previous two values, so we can skip the array entirely.

def climb_stairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

Five steps, three lines of useful code, O(n) time and O(1) space. The framework is the part that scales. The recurrence at the bottom of step 2 is the part that varies.

The six patterns I see over and over

Most DP problems in interviews and product code fall into one of six pattern families. Recognizing the family is half the battle.

When a new problem arrives, my first move is to figure out which family it lives in. "This involves two strings" pushes me toward subsequence DP. "This involves a capacity and a set of items" pushes me toward knapsack. "This involves an interval that I need to split" pushes me toward interval DP. The recurrence drops out of the family choice; I am rarely inventing the recurrence from scratch.

Memoization vs tabulation: pick one and know why

Once you have the recurrence, you have a choice. Top-down (memoized recursion) writes the recurrence directly with a cache. Bottom-up (tabulation) iterates from smallest to largest state, filling a table.

# Top-down (memoization)
from functools import lru_cache

@lru_cache(maxsize=None)
def climb(n):
    if n <= 1: return 1
    return climb(n - 1) + climb(n - 2)

# Bottom-up (tabulation)
def climb_tab(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Both are O(n) time and O(n) space. The difference is what trips you in production.

Top-down wins when the recurrence is natural to express recursively, when not all states are needed (sparse DP), and when you are still iterating on the design. It is the version I write first when prototyping a DP, because the code mirrors the math. The cost is recursion-stack depth (Python caps at ~1000, JavaScript engines vary but rarely allow more than a few thousand) and the constant factor of function-call overhead.

Bottom-up wins when you know all states will be visited, when stack depth would be a problem, when you want to optimize space (you cannot easily drop dimensions in a memoized recursion), and when the constant factor matters. Most production-grade DP code I have shipped is bottom-up. Most interview-prep DP code I have written is top-down because the framework maps to it more directly.

The rule I follow: prototype top-down, ship bottom-up. The translation from one to the other is mechanical once the recurrence is right.

Space optimization: the trick that drops a dimension

Many DPs only depend on the last row, the last two rows, or a small window. When that is true, you can drop the table dimension entirely and keep a few variables.

Grid DP for min path sum is a clean example. The full version is O(rows * cols) space. The optimized version walks the grid row by row keeping only the previous row, and is O(cols) space. If you only need the answer at the bottom-right, you can even do it with a single row updated in place (with care about the update order to avoid stomping values you still need).

Knapsack DP is another classic. The full version is O(n * W) where n is items and W is capacity. The optimized version uses a 1D array of size W + 1 and iterates capacities in reverse to avoid using an item twice. Drops a factor of n off the memory.

The optimization is not always worth it. If your input is small, the cleaner 2D version is more readable and the asymptotic memory does not matter. If your input is large enough that the table would not fit in cache (or worse, would not fit in RAM), the optimized version is the difference between code that runs and code that swaps to disk. Read the problem twice, decide whether n * W is something you can afford, and pick the version that matches.

Two anti-patterns that catch people

The single most common DP mistake I have seen: wrong state definition that makes the recurrence impossible. If you cannot write a clean recurrence in step 2, almost always the issue is that you missed a dimension in step 1. "Best time to buy/sell stock with cooldown" needs a state for the day and a state for whether you currently hold the stock and whether you are in cooldown. Try to do it with one dimension and you will write three buggy versions before you realize the state is incomplete.

The second: conflating recursion with DP. Recursion without memoization can still be DP-shaped, but it will time out. Recursion with memoization is DP. If your top-down code is exponential, you forgot the cache or your cache key is wrong (e.g. you cached on a mutable list that hashes differently each call).

Q&A: the seven questions I get most often

Instead of a recap, the genuinely useful version of an ending for an article like this is a Q&A. These are the questions I have been asked most by engineers learning DP, in roughly the order they come up.

Q1. "How do I know it is a DP problem?" A: It asks for an optimum (max, min, count of ways) over choices, and the brute-force solution has overlapping subproblems. If the brute force is fast enough, it is not a DP problem; it is just the brute force. DP is the optimization.

Q2. "How do I choose the state?" A: Write the brute-force recursion first. The arguments to the recursive function are your state. Trim arguments that do not affect the answer. What is left is the smallest state that captures the subproblem.

Q3. "My recurrence works on small input and times out on large input. Why?" A: You are probably recomputing without caching, or your cache key is mutable. Add memoization and check that the key is hashable and immutable.

Q4. "Should I learn top-down or bottom-up first?" A: Top-down. It maps to the framework more directly. Translate to bottom-up later when you need to optimize.

Q5. "When does space optimization matter?" A: When the table is bigger than your cache budget, or when memory is a hard constraint (embedded, real-time). For most product code, the unoptimized version is fine and more readable.

Q6. "Why does my DP give the right count but the wrong answer when reconstructing the solution?" A: Reconstruction needs you to remember the choice that was optimal at each state, not just the cost. Add a parent table or trace backwards from the final state using the recurrence.

Q7. "How long should it take me to feel comfortable with DP?" A: Solve fifteen problems following the framework explicitly (write all five steps for each one before coding). After fifteen, you will start recognizing patterns without thinking. After thirty, the framework runs in your head and you stop writing the steps down. There is no shortcut. There is also no magic; it is just reps.