Dynamic Programming Patterns: From Recursion to Tabulation, with 12 Problems

You can read five DP tutorials, nod along, and still freeze when a new problem shows up. That happens because most tutorials teach solutions instead of dynamic programming patterns. This post teaches the pattern.

You’ll start with a brute-force solution and watch it fail. Then you’ll turn it into a memoized solution, then a bottom-up table, then a space-optimized version. You’ll also get a way to recognize which of five DP families a problem belongs to, a dry-run trace, code templates in Python and C++, and 12 practice problems in difficulty order. For the complexity vocabulary used throughout, see our guide to time and space complexity.

Phase 1: The Problem (Why Brute Force Dies)

Here is a question you could get in an interview: given coins of denominations [1, 3, 4], what is the minimum number of coins that makes 6?

The natural recursive answer is: try every coin as the last coin, and solve the smaller amount that remains.

def min_coins(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return float("inf")
    return 1 + min(min_coins(coins, amount - c) for c in coins)

It’s correct, and it’s catastrophically slow. For amount 6 with coins [1, 3, 4], min_coins(coins, 2) gets computed again and again, once from every path that reaches 2. With a coin of value 1, the recursion can go as deep as amount, and each level branches n ways. The worst case is roughly O(nᵃᵐᵒᵘⁿᵗ). At amount 40 with three coins, that is far more calls than any machine will finish.

The key observation is that there are only amount + 1 distinct questions: “what’s the best for 0, for 1, for 2, …”. The brute force answers the same ones exponentially many times. Dynamic programming is the discipline of answering each distinct question once.

What most tutorials get wrong: they say “DP is recursion plus a cache” and move straight to filling tables. The mechanical part is the easy 20%. The hard 80% is defining the state, meaning deciding what the function’s arguments are, and that decision determines everything else. The sections below are organized around that decision.

Phase 2: The Pattern

The running analogy: a notebook in the margin

Imagine solving a long exam where many questions depend on earlier ones. Memoization is writing each answer in the margin the first time you derive it, so the next question that needs it just reads it. Tabulation is working through the questions in dependency order so that every answer you need is already written down before you need it. Both use the same notebook; they differ in who decides the order of work.

When to suspect DP: trigger phrases

DP needs two properties: overlapping subproblems (the same sub-question recurs) and optimal substructure (the best answer is built from best answers to smaller pieces). In problem statements, look for:

• “minimum / maximum / fewest / longest / cheapest …”
• “count the number of ways to …”
• “is it possible to … (true/false)”
• “at each step you may choose between a few options” (take or skip, left or right, which coin)
• Input is a sequence, grid, or set of items, and a greedy choice has an easy counterexample.

That last point matters. On coins [1, 3, 4] with amount 6, greedy picks 4+1+1 (three coins), while the optimum is 3+3 (two coins). If greedy had worked, you wouldn’t need DP. If you’re choosing between DP and a graph algorithm, compare with our Dijkstra walkthrough. DP on a DAG is shortest-path relaxation in topological order.

The five-step recipe

1. Define the state. What is the smallest set of parameters that fully describes a subproblem? (dp[a] = fewest coins for amount a.)
2. Write the recurrence. How does a state depend on smaller states? (dp[a] = 1 + min(dp[a - c]) over coins c.)
3. Set the base cases. (dp[0] = 0.)
4. Pick the order. Every state must be computed after the states it depends on.
5. Name the answer. Which state holds the final result? (dp[amount].)

Phase 3: Step-by-Step Walkthrough

We’ll trace two examples: the coin problem (1D) and longest common subsequence (2D).

Trace 1: Coin change, coins [1, 3, 4], amount 6

State: dp[a] is the fewest coins to make a. Recurrence: dp[a] = 1 + min(dp[a-c]) for each coin c ≤ a.

The answer is dp[6] = 2 (3+3), which greedy would have missed.

Trace 2: LCS of "ABCDE" and "ACE"

State: dp[i][j] is the LCS length of the first i characters of s1 and the first j of s2. If the characters match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise it is max(dp[i-1][j], dp[i][j-1]).

The answer is 3 ("ACE"). Notice that each cell reads only its left, upper, and upper-left neighbors, which tells you the iteration order (top to bottom, left to right) and that you only ever need two rows in memory.

Phase 4: Code Templates

All Python below uses only the standard library and runs on Python 3.9+ (functools.cache was added in 3.9, per the Python docs).

Template A: the full evolution on one problem (Climbing Stairs)

You can climb 1 or 2 steps at a time. How many ways to reach step n?

from functools import cache

# 1) Brute force: O(2^n) time
def ways_brute(n):
    if n <= 1:
        return 1
    return ways_brute(n - 1) + ways_brute(n - 2)

# 2) Top-down memoization: O(n) time, O(n) space (+ recursion stack)
def ways_memo(n):
    @cache
    def go(i):
        if i <= 1:
            return 1
        return go(i - 1) + go(i - 2)
    return go(n)

# 3) Bottom-up tabulation: O(n) time, O(n) space
def ways_tab(n):
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 4) Space-optimized: O(n) time, O(1) space
def ways_opt(n):
    prev, cur = 1, 1
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur
    return cur

What problem it solves: it shows that all four versions encode the same recurrence. Only the evaluation strategy changes.

Key parts: @cache is an unbounded memo wrapper, and the Python docs describe it as the same as lru_cache(maxsize=None). The tabulated loop runs in increasing i because dp[i] depends only on smaller indices. The O(1) version works because dp[i] needs only the last two values.

Production notes: Python’s default recursion limit is 1000 frames, so ways_memo(5000) raises RecursionError. Either raise the limit (risky: deep recursion can crash the interpreter) or use tabulation. Cached function arguments must be hashable, so you can’t pass a list as state. Convert to a tuple or an index. The cache also keeps references to everything it has seen until you clear it, so in a long-running service prefer a local cache that dies with the call, as above.

Template B: 1D unbounded DP (Coin Change), Python and C++

def coin_change(coins, amount):
    INF = amount + 1                 # sentinel larger than any valid answer
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] >= INF else dp[amount]   # O(amount * len(coins)) time, O(amount) space

#include <vector>
#include <algorithm>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);   // sentinel = amount + 1
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];  // O(amount * n) time, O(amount) space
}

What problem it solves: minimizing the count of items from an unlimited supply to hit a target.

Key parts: the sentinel amount + 1 stands for “unreachable” and can never win a min against a real answer (the worst real answer is amount coins of value 1). Using INT_MAX in C++ would overflow on dp[a-c] + 1.

Production notes: the same shape (a target sum with a choice per step) appears in budget allocation and packing problems. The cost is linear in the target value, not in the input size, so for huge targets (say 10⁹) this “pseudo-polynomial” solution is unusable.

Template C: 2D DP with rolling rows (LCS)

def lcs(a: str, b: str) -> int:
    if len(b) > len(a):               # keep the shorter string as the row
        a, b = b, a
    prev = [0] * (len(b) + 1)
    for ch in a:
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if ch == b[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]   # O(m*n) time, O(min(m,n)) space

What problem it solves: comparing two sequences where order matters but gaps are allowed.

Key parts: cur[j] reads prev[j-1], prev[j], and cur[j-1], which is exactly the left, up, and up-left neighbors from the trace.

Production notes: rolling rows cut memory from O(mn) to O(min(m,n)) but throw away the table you’d need to reconstruct the subsequence itself. If you need the actual string, keep the full table (or use Hirschberg’s divide-and-conquer trick, which is beyond this post).

Template D: 0/1 knapsack in one array (Partition Equal Subset Sum)

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):   # BACKWARD so each item is used once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]   # O(n * target) time, O(target) space

What problem it solves: deciding whether some subset hits an exact sum, where each item can be used at most once.

Key parts: the inner loop direction is the whole trick. Going backward means dp[s - x] still holds the value from before this item was processed. Going forward would let the same item count repeatedly, which silently turns 0/1 knapsack into the unbounded version (Template B’s behavior).

Production notes: this is the classic bug that passes small tests and fails hidden ones. Subset-sum style DP is also the reason “pseudo-polynomial” appears in discussions of NP-hardness. The runtime depends on the numeric value of target.

Phase 5: Variations (The Five Families)

Almost every interview DP problem is one of these. Identify the family, and the state design is mostly done.

1. Linear DP (state = a position). dp[i] depends on a fixed number of earlier positions. Example, House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Take house i and skip its neighbor, or skip house i.

2. Grid DP (state = a cell). dp[r][c] depends on the cells above and to the left. Example, Unique Paths: dp[r][c] = dp[r-1][c] + dp[r][c-1], with the first row and column all 1s. Obstacles just set a cell to 0.

3. Knapsack DP (state = item index + remaining capacity). Each item is take-or-skip. Example: Template D (0/1) versus Template B (unbounded). The only difference is the loop direction and whether you keep an item index.

4. Two-sequence DP (state = a prefix of each sequence). Example, Edit Distance: dp[i][j] is the cost to turn the first i characters of s into the first j of t. On a mismatch, take 1 + min(dp[i-1][j] (delete), dp[i][j-1] (insert), dp[i-1][j-1] (replace)). On a match, copy dp[i-1][j-1].

5. Interval DP (state = a range [l, r]). The answer for a range is built by splitting it at some point k. Example, Burst Balloons: dp[l][r] is the best score from bursting everything strictly between l and r, trying each balloon k as the last one burst. Iterate by increasing interval length. The “last, not first” framing is the insight that makes the subproblems independent.

When the answer is built from a contiguous window rather than a choice at each step, you may want a different tool, so compare with our sliding window problems.

Phase 6: Practice Problems (Easy to Hard)

Problem numbers are LeetCode’s. Solve them in this order.

Phase 7: Common Mistakes and Edge Cases

• Wrong state, not wrong code. If you can’t write a clean recurrence, the state is missing information or has too much. Ask what the future needs to know about the past, and nothing more.
• Off-by-one in table size. Prefix-style DP needs n + 1 rows and columns so that index 0 means “empty prefix”. Mixing 0-based string indexing with 1-based table indexing (b[j-1] versus dp[j]) is the most common slip.
• Sentinel overflow. INT_MAX + 1 overflows in C++ and Java. Use amount + 1 or a guarded check.
• Loop direction in 1D knapsack. Backward for 0/1, forward for unbounded. Test with one item that fits twice to catch it.
• Empty input. Amount 0 should return 0 (not -1). Empty strings should give an LCS of 0 and an edit distance of the other string’s length. Your base cases should handle these without special-casing.
• Duplicates. For counting problems (Coin Change II style), loop order decides whether [1,2] and [2,1] count as the same combination. Items-outer counts combinations, amount-outer counts ordered sequences.
• Overflow in counting DP. Path and ways counts grow fast. Use 64-bit integers or a modulus when the problem says so (Python integers don’t overflow, but C++ and Java do).
• Recursion depth. Memoized recursion on a sequence of length 10⁵ will blow Python’s stack. Convert to tabulation.
• Mutable or unhashable state in a cache. Pass indices or tuples, not lists. Never wrap a function with side effects in a cache.

Phase 8: Where This Appears in Real Systems

These are well-established, widely documented uses. Verify citations before publishing (see fact-check notes).

• Edit distance in text tools. The Wagner–Fischer algorithm is the dynamic program behind fuzzy matching and spelling suggestions. It is the same recurrence as problem 10, and production systems usually add a cutoff so they don’t compute the full table for hopeless candidates.
• Sequence alignment in bioinformatics. Needleman–Wunsch (global) and Smith–Waterman (local) are two-sequence DP with scoring matrices. They’re the textbook example of the same grid-shaped table as LCS, with different transition scores.

Other well-known DP-family algorithms include the Viterbi algorithm for decoding hidden Markov models, which was historically central to speech recognition and sequence tagging, and the Knuth–Plass line-breaking algorithm used by TeX. File-diff tools are related: classic diff is framed around LCS, though Git’s default diff uses Myers’ algorithm, a shortest-edit-script method on the same edit graph, not the standard O(mn) table.

If you’re prepping for interviews, DP shows up across the board in the loops described in our AI engineer career roadmap, because it tests whether you can model a problem before coding it.

Key Takeaways

• DP is for problems with overlapping subproblems and optimal substructure. Greedy failing on a small counterexample is your cue.
• State design is the real skill. Memoization and tabulation are two ways to evaluate the same recurrence.
• Follow the recipe: state, recurrence, base cases, order, answer.
• Most problems fall into five families: linear, grid, knapsack, two-sequence, interval.
• In 1D knapsack, loop direction decides 0/1 versus unbounded. Backward means each item is used once.
• Rolling arrays save memory but cost you the ability to reconstruct the solution.
• Memoized recursion is simplest to write, but tabulation avoids Python’s recursion limit and is usually easier to space-optimize.

FAQ

What is the difference between memoization and tabulation?
Memoization is top-down: you write the recursion and cache results as you go, computing only the states you actually need. Tabulation is bottom-up: you fill a table in dependency order. Both have the same asymptotic time for most problems, but tabulation avoids recursion-depth limits and makes space optimization more natural.

How do I know if a problem needs dynamic programming?
Look for “minimum”, “maximum”, “count the ways”, or “is it possible” combined with repeated choices, and check whether a brute-force recursion recomputes the same arguments. If a simple greedy choice has a counterexample, DP is likely the answer.

Is dynamic programming the same as recursion?
No. Recursion is a way of structuring code. DP is an optimization strategy that avoids recomputation. Plain recursion on fib or coin change is exponential, while the same recurrence with a cache or table is polynomial.

Why does my DP work on examples but time out?
Usually the state has too many dimensions, or you’re recomputing instead of reusing a table entry. Count your states and the work per state. If states × transitions is too large, look for a smaller state or a faster transition (for example, the O(n log n) LIS approach).

Should I learn top-down or bottom-up first?
Start top-down. It maps directly onto how you’d think about the problem, and the recurrence falls out naturally. Convert to bottom-up once you understand the dependency order, especially for deep inputs.