Dynamic Programming

Learning Objectives

By the end of this page, you should be able to:

• Define dynamic programming and identify the two properties (overlapping subproblems, optimal substructure) that make a problem a DP candidate.
• Explain the difference between memoization (top-down) and tabulation (bottom-up), and implement both.
• Trace and code the 0/1 Knapsack and Longest Common Subsequence (LCS) solutions, including their DP tables.
• Analyze the time and space complexity of a DP solution, and apply space optimization (rolling array) where possible.
• Distinguish dynamic programming from divide-and-conquer and greedy algorithms, and justify when each applies.

Quick Answer

Dynamic programming (DP) is a technique for solving problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing (caching) the result for reuse. It matters because many problems — like Fibonacci numbers, shortest paths, or resource allocation — have a naive recursive solution that recomputes the same subproblem exponentially many times. DP turns that exponential blowup into polynomial time by trading extra memory for speed. There are two ways to implement DP: memoization, which caches results inside a top-down recursion, and tabulation, which builds results iteratively from the smallest subproblem upward. Both rely on a problem having optimal substructure — the optimal answer can be built from optimal answers to smaller pieces.

Why Dynamic Programming Exists

Think about computing the 40th Fibonacci number with plain recursion: fib(n) = fib(n-1) + fib(n-2). If you draw the call tree, fib(38) gets computed twice, fib(37) three times, and so on — the tree has roughly 2^n nodes. Almost all of that work is wasted because the same subproblem is solved over and over. DP's entire premise is simple: if you're going to solve the same subproblem multiple times, solve it once and remember the answer.

For this to pay off, a problem needs two properties:

1. Overlapping subproblems — the recursive breakdown revisits the same smaller inputs repeatedly (unlike, say, merge sort, where each recursive call works on a distinct, non-overlapping slice of the array).
2. Optimal substructure — the optimal solution to the full problem can be assembled from optimal solutions to its subproblems. If the best way to solve the big problem doesn't depend on the best way to solve the small ones, DP won't help.

Memoization (Top-Down)

Memoization keeps the natural recursive structure of the brute-force solution but adds a cache (a dictionary or array) that stores the result of each subproblem the first time it's computed. Every later call with the same input returns the cached value instantly instead of recursing again.

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(40))  # 102334155, computed in O(n) instead of O(2^n)

Trace it by hand for fibonacci(4): the call tree branches into fib(3) and fib(2), but by the time fib(3) needs fib(2), it's already in the memo, so that branch is cut short. Only n+1 distinct subproblems ever get computed.

Why it matters: memoization is the easiest way to convert an exponential brute-force recursion into a polynomial one, often by adding just 2-3 lines of code.

Common misunderstanding: students often think memoization changes the algorithm's logic. It doesn't — it only changes how many times the same computation happens. The recursive relation stays identical to the brute-force version.

Tabulation (Bottom-Up)

Tabulation flips the direction: instead of recursing down from n and caching along the way, you start at the smallest subproblems and iteratively build up to the answer, storing every intermediate result in a table (usually an array).

def fibonacci(n):
    if n <= 1:
        return n
    fib_table = [0] * (n + 1)
    fib_table[1] = 1
    for i in range(2, n + 1):
        fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
    return fib_table[n]

print(fibonacci(10))  # 55

Because tabulation is iterative, it avoids recursion's call-stack overhead entirely — no risk of stack overflow for large n. It's also often easier to space-optimize, since you frequently only need the last one or two rows of the table (see below).

Real-world example: a spreadsheet is essentially bottom-up tabulation. Filling cell C10 as =C9+C8 and dragging it down the column is exactly the tabulation pattern — each cell (subproblem) is computed once, in order, from the ones before it.

Common misunderstanding: students often assume tabulation is "always faster" than memoization. Asymptotically they're the same — both compute each of the n subproblems once. Tabulation just tends to have lower constant-factor overhead because it skips function-call machinery.

Worked Example: 0/1 Knapsack

Given n items, each with a weight and value, and a knapsack capacity W, choose a subset of items (each used at most once) that maximizes total value without exceeding W.

Optimal substructure: for each item, you either include it or you don't. If you include item i, the remaining problem is "fill capacity W - weight[i] optimally using items 1..i-1." That's a smaller instance of the same problem — the hallmark of DP.

def knapsack(weights, values, W):
    n = len(weights)
    # dp[i][w] = best value using first i items with capacity w
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # exclude item i-1
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                                dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print(knapsack(weights, values, 7))  # 9 (items with weight 3 and 4)

Each cell dp[i][w] answers "what's the best value using the first i items within capacity w?" — and it's built entirely from cells already computed (dp[i-1][...]), which is exactly tabulation in action.

Worked Example: Longest Common Subsequence (LCS)

Given two strings, find the length of the longest subsequence (not necessarily contiguous) common to both. Example: LCS of "ABCBDAB" and "BDCABA" is "BCBA" (length 4).

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

print(lcs("ABCBDAB", "BDCABA"))  # 4

Why it matters: LCS underlies diff tools (comparing file versions), DNA sequence alignment in bioinformatics, and spell-checkers computing edit distance variants.

Complexity Comparison

Problem	Naive (no DP)	With DP (time)	With DP (space)	Space-optimized
Fibonacci(n)	O(2^n)	O(n)	O(n)	O(1) — keep last 2 values
0/1 Knapsack (n items, capacity W)	O(2^n)	O(n·W)	O(n·W)	O(W) — one row at a time
LCS (strings of length m, n)	O(2^(m+n))	O(m·n)	O(m·n)	O(min(m,n)) — two rows
Matrix Chain Multiplication (n matrices)	O(2^n) roughly	O(n^3)	O(n^2)	—

The space-optimization trick works whenever dp[i][...] only depends on dp[i-1][...] (or a fixed number of previous rows) — you don't need to keep the whole table, just the last row or two, rolling them as you go.

Subproblem Dependency Flow

Without memoization, fib(3) and fib(2) would each be recomputed from scratch every time they appear. With memoization or tabulation, the highlighted nodes are computed once and reused — turning the exponential tree into a linear chain of n unique subproblems.

Real-World Applications

• Version control diffs (git diff) use LCS-based algorithms to find the minimal set of changes between file versions.
• Route planning and network routing — Bellman-Ford, a DP algorithm, finds shortest paths in graphs that may have negative edge weights (used in some routing protocols).
• Resource allocation and budgeting — knapsack-style DP models "which projects to fund within a budget to maximize return."
• Bioinformatics — sequence alignment for DNA/protein comparison is a direct application of edit-distance DP, a close cousin of LCS.
• Compilers and NLP — CYK parsing and word-break/segmentation problems use DP to determine valid structure efficiently.

Key Terms

Term	Definition
Overlapping subproblems	The property where a recursive breakdown of a problem revisits the same smaller inputs multiple times
Optimal substructure	The property where an optimal solution to a problem can be constructed from optimal solutions to its subproblems
Memoization	Top-down DP: recursion plus a cache that stores results of subproblems as they're first computed
Tabulation	Bottom-up DP: iteratively filling a table from the smallest subproblems up to the final answer
DP table	The array (1D, 2D, or higher) used to store subproblem results in tabulation
State	The set of parameters that uniquely identifies a subproblem (e.g., (i, w) in knapsack)
Space optimization	Reducing a DP table's memory footprint by keeping only the rows/values still needed
Base case	The smallest subproblem(s) whose answer is known directly, without further recursion

Common Mistakes

Misconception	Why It's Wrong	Correct Understanding
"Dynamic programming means using dynamic arrays or dynamic memory."	The name is historical (coined by Richard Bellman in the 1950s) and has nothing to do with dynamic memory allocation.	DP refers to solving problems via cached subproblem reuse; the name is a misnomer that stuck.
"Any recursive problem can be sped up with memoization."	Memoization only helps when subproblems actually overlap. If every recursive call operates on a distinct input (like merge sort), there's nothing to cache — memoization adds overhead for no benefit.	Check for overlapping subproblems first. If the recursion tree has no repeated nodes, DP doesn't apply; consider divide-and-conquer instead.
"Tabulation and memoization always give the same time complexity, so it doesn't matter which one you pick."	While both are typically the same asymptotic complexity, tabulation can enable space optimization (rolling arrays) that memoization's call stack makes awkward, and memoization can skip subproblems tabulation would compute unnecessarily.	Choose based on context: memoization is more natural when not all subproblems are needed; tabulation is better when you want iterative code or aggressive space optimization.

Comparison and Connections

Aspect	Memoization (Top-Down)	Tabulation (Bottom-Up)
Direction	Starts at the original problem, recurses down	Starts at base cases, builds up
Implementation	Recursion + cache	Iteration + table
Computes unnecessary subproblems?	No — only computes what's needed	Sometimes — may fill table entries never used
Stack overflow risk	Yes, for large inputs (deep recursion)	No — purely iterative
Easy to space-optimize?	Harder (call stack in the way)	Easier (roll over previous rows)

Paradigm	Subproblems	Typical Use Case
Dynamic Programming	Overlapping, solved once and cached	Fibonacci, Knapsack, LCS, shortest paths with cycles/negative weights
Divide and Conquer	Independent, non-overlapping	Merge sort, quicksort, binary search
Greedy	No subproblem reuse; makes locally optimal choice at each step, never revisited	Activity selection, Huffman coding, Dijkstra's shortest path (non-negative weights)

Practice Questions

Recall

1. What two properties must a problem have for dynamic programming to apply? Answer: Overlapping subproblems and optimal substructure.
2. What is the difference between memoization and tabulation? Answer: Memoization is top-down — recursion with a cache; tabulation is bottom-up — iterative table-filling from base cases upward.

Understanding

3. Why does plain recursive Fibonacci take O(2^n) time, while the memoized version takes O(n)? Answer: Without caching, the recursion tree recomputes the same fib(k) values exponentially many times. Memoization ensures each of the n distinct subproblems is computed exactly once, then reused in O(1) per repeat lookup.
4. Why doesn't dynamic programming help speed up merge sort? Answer: Merge sort's subproblems (left half, right half) never overlap — each recursive call works on a completely distinct slice of the array, so there's nothing to cache or reuse.

Application

5. You need to fill a knapsack of capacity 7 with items of weights [1,3,4,5] and values [1,4,5,7]. Trace dp[i][w] for i=2, w=4 in the knapsack code above. Answer: At i=2 (item weight 3, value 4), w=4: dp[2][4] = max(dp[1][4], dp[1][1] + 4) = max(1, 0+4) = 4.
6. A word-processor's spell-checker needs to compute the minimum number of edits (insert/delete/substitute) to turn one word into another. What DP technique would you use, and what would the state represent? Answer: Edit distance DP, a close relative of LCS. The state dp[i][j] represents the minimum edits to convert the first i characters of word A into the first j characters of word B.

Analysis

7. Compare the space complexity of the naive 2D knapsack table versus a space-optimized 1D version. Why does the optimization work? Answer: The 2D table uses O(n·W) space, storing dp[i][w] for all i. Since dp[i][w] only ever depends on row i-1, you can collapse it to a single 1D array of size W+1, updated in place by iterating w from high to low (to avoid overwriting values still needed from the "previous row"). This reduces space to O(W).
8. A classmate says, "Since DP is more powerful than greedy, I should always use DP instead of greedy when both seem to apply." Evaluate this claim. Answer: False in general. Greedy algorithms are typically faster (O(n log n) or O(n)) than the DP alternative (often O(n^2) or worse) when a greedy-choice property actually holds — e.g., Dijkstra's algorithm on non-negative-weight graphs. DP is more broadly applicable (it works even when greedy's locally-optimal choice doesn't guarantee a globally optimal one) but that generality often costs time and space. Choose greedy when you can prove the greedy-choice property holds; otherwise fall back to DP.

FAQ

Is dynamic programming the same as recursion? No. Recursion is just a way of expressing a problem in terms of smaller instances of itself. DP is a strategy for avoiding redundant recursive work by caching subproblem results — it can use recursion (memoization) or replace it with iteration (tabulation).

Why is it called "dynamic programming" if there's nothing dynamic about it? It's a historical accident. Richard Bellman named it in the 1950s partly to make his research sound impressive to funders — "programming" here means "planning/tabulation," not computer programming.

How do I recognize a DP problem in an interview? Look for phrases like "minimum/maximum number of ways," "optimal value subject to constraints," or a brute-force recursive solution with visibly repeated subproblems. If you can write a recurrence relation (the answer to the big problem in terms of smaller versions of itself) and those subproblems overlap, it's DP.

Should I always start with memoization or tabulation? Start with memoization — write the brute-force recursive solution first, verify it's correct, then add a cache. It's usually easier to get right. Convert to tabulation afterward if you need to avoid recursion depth limits or want to space-optimize.

Does DP always guarantee a polynomial-time solution? Not always. DP guarantees you solve each distinct subproblem once, but if the number of distinct subproblems (states) is itself exponential (e.g., subsets of a set), the DP solution can still be exponential — just less redundant than brute force. Always check how many distinct states exist.

What's the difference between 1D and 2D DP? It depends on how many parameters uniquely define a subproblem's "state." Fibonacci needs just n (1D: dp[n]). Knapsack needs both item index and remaining capacity (2D: dp[i][w]). Some problems (like certain string-matching variants) need 3 or more dimensions.

Quick Revision

• DP solves problems with overlapping subproblems + optimal substructure by caching subproblem results.
• Memoization = top-down recursion + cache (dictionary/array).
• Tabulation = bottom-up iteration, filling a table from base cases upward.
• Naive recursive Fibonacci: O(2^n). DP Fibonacci: O(n) time, O(n) space, or O(1) space optimized.
• 0/1 Knapsack DP: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]); O(n·W) time and space.
• LCS DP: match → dp[i-1][j-1]+1; no match → max(dp[i-1][j], dp[i][j-1]); O(m·n) time and space.
• Divide-and-conquer has non-overlapping subproblems (merge sort); greedy makes irrevocable locally-optimal choices with no subproblem caching.
• Space optimization: if dp[i] only depends on dp[i-1], keep just the last row/values instead of the full table.
• Memoization risks stack overflow on deep recursion; tabulation avoids this by being iterative.
• "Dynamic programming" is a historical name — it has nothing to do with dynamic memory.
• Real applications: git diff (LCS), Bellman-Ford routing, DNA sequence alignment, budget/resource allocation.

Related Topics

Prerequisites

• Recursion and the call stack
• Big-O time and space complexity analysis
• Basic array and 2D array manipulation

Related Topics

• Divide and Conquer algorithms
• Greedy algorithms
• Graph shortest-path algorithms (Bellman-Ford, Floyd-Warshall)

Next Topics

• Advanced DP patterns: bitmask DP, digit DP, DP on trees
• String algorithms: edit distance, sequence alignment
• Optimization problems: Matrix Chain Multiplication, Coin Change