Dynamic Programming

Definition: An algorithmic optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem exactly once, and storing (caching) their solutions for reuse.

How It Works

Dynamic programming (DP) applies when a problem has two properties:

Overlapping subproblems: the same smaller subproblem recurs many times during a naive recursive solution, so recomputing it repeatedly wastes work.
Optimal substructure: an optimal solution to the whole problem can be built from optimal solutions to its subproblems.

Two equivalent implementation strategies exploit this:

Memoization (top-down): write the recursive solution normally, then wrap it with a cache (hash map or array) keyed by the subproblem’s parameters. Before recursing, check the cache; after computing, store the result. Recursive calls that were already solved short-circuit immediately.
Tabulation (bottom-up): build an explicit table iteratively, starting from base cases and filling toward the target answer. This typically uses less memory overhead than the recursive version, since it avoids call-stack frames entirely, and it’s often faster in practice due to no function-call overhead.

State design is the core skill in DP: identifying exactly what parameters uniquely define a subproblem (the “state”) determines both correctness and the size of the resulting DP table. Missing a dimension the answer actually depends on produces code that runs and often looks correct on simple inputs, but silently returns wrong answers on others.

Space optimization is common once correctness is established. Many DP recurrences only depend on the previous row or a small constant number of previous states, letting an O(n*m) table collapse to an O(m) rolling array, since older rows are never referenced again once the next row is computed.

Complexity Analysis

Approach	Time	Space
Naive recursion (no caching)	Often O(2^n) or worse	O(n) call stack
Memoized (top-down)	O(states * work per state)	O(states) cache + O(depth) call stack
Tabulated (bottom-up)	O(states * work per state)	O(states), often reducible to O(1 dimension)

“States” here means the number of distinct subproblems; for a classic 2D DP like edit distance between strings of length m and n, that’s O(mn) states, each doing O(1) work, for O(mn) total time.

Why It Matters

Transforms exponential O(2^n) brute-force recursive solutions, like naive Fibonacci or naive subset-sum, into polynomial time, often O(n) or O(n^2), by eliminating redundant recomputation.
Standard technique behind real production systems: diff/version-control tools use DP (edit distance) to compute minimal changesets between file versions, and DNA sequence alignment tools use the same Longest Common Subsequence recurrence to align genetic sequences.
Forms one of the core algorithm-design paradigms taught alongside greedy algorithms and divide-and-conquer, and is a frequent focus in technical interviews because it specifically tests the ability to recognize hidden recursive structure in a problem statement.

Common Pitfalls

Attempting DP on problems lacking optimal substructure; “longest simple path in a general graph” is NP-hard precisely because the greedy/DP substructure assumption breaks down in the presence of cycles.
High space complexity if the table size is unoptimized; a naive 2D table for a problem solvable with a rolling 1D array wastes memory that matters at scale, e.g. O(n) vs O(n*m) for edit distance on very large strings.
Defining the DP state incorrectly, missing a dimension the answer actually depends on, produces code that runs but silently returns wrong answers on certain inputs while passing on simpler test cases.
Off-by-one errors in base cases (dp[0] vs dp[1] indexing) are the single most common source of bugs in tabulated DP implementations.
Confusing “the problem has recursion” with “the problem has DP structure”; recursion without overlapping subproblems (e.g. plain binary search) gains nothing from memoization and adds unnecessary overhead.

Comparison

	Dynamic Programming	Greedy Algorithms	Divide and Conquer
Revisits subproblems	Yes, explicitly cached	No, one pass, no backtracking	Yes, but non-overlapping
Guarantees optimal result	Yes, if structure holds	Only when greedy-choice property holds	Yes, for problems it applies to
Typical complexity	Polynomial, from exponential brute force	Often O(n log n) or O(n)	O(n log n) typically
Example	Knapsack, edit distance	Dijkstra, Huffman coding	MergeSort, QuickSort

Example

Calculating Fibonacci numbers, the 0/1 Knapsack problem, and Longest Common Subsequence are canonical DP problems. Naive recursive Fibonacci recomputes the same subproblems repeatedly:

fib(5) -> fib(4) + fib(3)
fib(4) -> fib(3) + fib(2)   # fib(3) computed again
fib(3) -> fib(2) + fib(1)   # fib(2) computed again

Memoizing with a cache = {} cuts this from O(2^n) calls to O(n): each fib(k) is computed exactly once and reused thereafter, turning roughly 15 redundant recursive calls for fib(5) into exactly 6 unique computations. The bottom-up equivalent builds the same result iteratively:

dp[0], dp[1] = 0, 1
for i in 2..n: dp[i] = dp[i-1] + dp[i-2]

using only O(n) time and, with the rolling-variable optimization (a, b = b, a+b), O(1) space instead of an O(n) table.

Recognizing a DP Problem

A rough checklist for spotting when DP applies:

The problem asks for an optimum (min/max/count of ways), not just “does a solution exist.”
A brute-force recursive solution is easy to write but visibly recomputes the same inputs, e.g. the same (i, j) pair appears in the call tree many times.
Decisions made early in the problem constrain, but don’t fully determine, decisions made later, and the “state” needed to make a later decision correctly can be captured in a small fixed set of parameters.

If any of those don’t hold, e.g. the problem is really about existence and greedy suffices, or the recursive calls don’t actually overlap, DP is either unnecessary or the wrong tool.

Two Classic DP Problems, Briefly

0/1 Knapsack: given items with weight and value, and a capacity limit, maximize total value without exceeding capacity, each item used at most once. State: dp[i][w] = max value using the first i items with capacity w. O(items * capacity) time and space.
Longest Common Subsequence (LCS): given two strings, find the length of the longest subsequence common to both. State: dp[i][j] = LCS length of the first i characters of string A and first j characters of string B. O(m * n) time and space, and the same recurrence underlies diff tools and DNA alignment.

LCS, Traced on a Small Example

Finding the LCS of "ABC" and "AC". dp[i][j] = LCS length of the first i characters of string A ("ABC") and first j characters of string B ("AC"). Recurrence: if the characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

        ""   A   C
    ""   0   0   0
    A    0   1   1
    B    0   1   1
    C    0   1   2

Row B, column C: B != C, so dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1. Row C, column C: C == C, so dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2. The final answer, dp[3][2] = 2, matches the actual LCS "AC".

Variants

Memoization vs. tabulation, covered above under How It Works, are the two standard implementation strategies; memoization only computes states actually reachable from the starting call, while tabulation computes every state in the table regardless of whether it’s needed, which can waste work on some problems but avoids recursion overhead entirely.
Digit DP: a specialized state design for counting numbers with certain digit-level properties within a range, where the state tracks digit position, a “tight” flag (whether the prefix so far equals the range bound’s prefix), and problem-specific accumulated info.
Bitmask DP: used when the state needs to track a subset of a small set of items (commonly up to about 20), encoding the subset as an integer bitmask, common in variants of the traveling salesman problem and assignment problems.
DP on trees: recurrence defined over a tree’s parent-child structure instead of a linear index, computed via a post-order traversal so each node’s DP value is derived from its already-computed children.

FAQ

Is DP always the same as memoized recursion? No. Memoized recursion is one implementation strategy (top-down); tabulation (bottom-up) solves the exact same recurrence without any recursion. Both are “dynamic programming” in the sense of exploiting overlapping subproblems and optimal substructure.

How do you decide the space complexity of a DP solution can be reduced? Check whether the recurrence for dp[i][...] only references dp[i-1][...] (or a small constant number of previous rows/states). If so, only those rows need to be kept, collapsing the table to a rolling window instead of the full history.

Why do interviewers care so much about DP specifically? Because spotting hidden overlapping-subproblem structure in a problem statement that doesn’t obviously look recursive is a genuinely transferable skill, unlike memorizing a specific algorithm, and it tests both problem decomposition and complexity reasoning at once.

Real-World Systems

diff and other version-control tools compute the edit distance (or LCS) between file versions using the same DP recurrence shown above, to produce a minimal, human-readable changeset.
DNA and protein sequence alignment tools (e.g. the Needleman-Wunsch and Smith-Waterman algorithms in bioinformatics) are directly built on the LCS/edit-distance DP recurrence, scored with domain-specific match/mismatch penalties.
Compilers use DP-style techniques in instruction selection (finding the cheapest sequence of machine instructions for an expression tree) and in register allocation heuristics.
Spell-checkers and fuzzy-matching search features compute Levenshtein (edit) distance via DP to rank candidate corrections by how many single-character edits separate them from the input.

Referenced by

Dig deeper

Spot an error in this note?