Dynamic programming solves a problem by combining answers to smaller versions of the same problem. It is a technique, not a single algorithm, and it applies to problems with two structural properties:

Optimal substructure: the answer to the full problem can be expressed in terms of answers to strictly smaller subproblems. This is the correctness condition. Without it, the recurrence does not even make sense.
Overlapping subproblems: the same subproblems appear in many branches of the recursion. This is the efficiency condition. Without it, memoization buys nothing and plain recursion or divide-and-conquer is already optimal.

Both must hold for DP to apply. Merge sort has optimal substructure but no overlap (each subproblem is solved once), so it is divide-and-conquer, not DP. Naive recursive Fibonacci has both, so memoization cuts it from O(2^n) to O(n).

Optimal Substructure

A common loose example is "the shortest path from A to C is the shortest path from A to B plus the shortest path from B to C." That is only correct when minimized over the intermediate vertex B:

shortest(A, C) = min over intermediate B of (shortest(A, B) + shortest(B, C))

The unquantified version is misleading and a common source of incorrect recurrences. Whenever you write a DP recurrence, ask: "What is the choice being optimized over?" That choice is usually a min or max over a set of predecessors, and it must appear in the recurrence explicitly.

Overlapping Subproblems

fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). The subtree fib(3) appears twice. Without memoization, every layer doubles the work; with memoization, each unique subproblem is solved once.

The two orange fib(3) nodes are the same subproblem evaluated twice. The yellow fib(2) nodes are the same subproblem evaluated three times. As n grows, every distinct subproblem appears exponentially often. The fix is to compute each one once and store the answer.

Memoization vs Tabulation

There are two ways to compute each subproblem exactly once:

Memoization (top-down): write a natural recursive function. Add a cache. On entry, check the cache; on exit, populate it. The first call kicks off a depth-first traversal of the dependency graph, and the cache stops repeated work.
Tabulation (bottom-up): choose an order for the subproblems such that each depends only on earlier ones. Fill a table in that order. The loop structure makes the dependency order explicit.

The two compute the same answers and have the same asymptotic complexity. They differ in constants and in what they make easy:

Aspect	Memoization	Tabulation
Code shape	Recursive function with a cache	Nested loops over the DP table
Iteration order	Implicit (driven by recursion)	Explicit (you write it)
Stack usage	O(recursion depth)	O(1) extra
Pruning	Free: unreached states are not computed	All states are computed, even unreachable ones
Space optimization	Hard	Easy (drop dimensions that are no longer needed)
Debugging	Easier (one subproblem at a time)	Easier (table is fully visible)

Memoization is usually the first version you write because it follows directly from the recurrence. Tabulation is usually the version you ship because it is easier to space-optimize and has no risk of stack overflow on deep recursions.

DP As A DAG

A DP problem can be modeled as a directed acyclic graph (DAG) of subproblems. Each node is a state. Each edge A -> B means "computing A depends on having computed B." Base cases are sinks (no outgoing edges); the final answer lives at some specified node or is aggregated over a set of nodes.

Green nodes are base cases. The blue node is the final answer. The structure is acyclic by construction: a cycle would mean a subproblem depends on itself, which makes the recurrence ill-defined.

Tabulation walks this DAG in topological order, computing each node after its dependencies. Memoization walks it in some depth-first order from the answer toward the base cases, caching each node as it is finished. Both touch each node exactly once.

A DP table dp[i] stores the value at node i in this graph.

Designing The State

The hardest step in any DP problem is picking the state: which variables uniquely determine a subproblem. The recurrence and the iteration order follow from the state, but the state itself rarely follows from a checklist. A few heuristics help:

The state must capture everything the future depends on. If two different paths arrive at the same (i, j, ...) and the rest of the computation can produce different answers from them, the state is missing a dimension.
If a greedy ordering matters, include the last choice in the state. TSP needs (mask, last_visited) because the cost of the next step depends on where you currently are.
If a constraint counts something, the count goes in the state. Best Time to Buy and Sell Stock IV needs a transactions used axis because the answer is bounded by the count.
If the problem distinguishes "doing something" from "having just done it," add a flag. Stock with Cooldown needs a sold state separate from not holding because the cooldown is a forced one-day commitment.
State should be as small as possible but no smaller. Adding a dimension multiplies the work; missing one breaks correctness. Always check: can two reachable executions land on the same state with different downstream answers? If yes, the state is too small.

A good state definition makes the recurrence obvious. When the recurrence is hard to write, the state is usually wrong.

The Recipe: Brute Force To DP

A reliable workflow for unfamiliar DP problems:

Write a brute-force recursion. Forget about efficiency. Define solve(state) that explores every choice from the current position and returns the answer for that subproblem. No memoization, no caching. The point is to express the recurrence in code.
Check for overlapping subproblems. Print the (state) argument inside solve. If the same state is hit more than once, DP applies. If every call is on a unique state, the problem is divide-and-conquer or backtracking, not DP.
Add memoization. Cache results by state. This step alone usually cuts exponential brute force to polynomial. The code stays recursive; you have a correct DP solution.
Convert to tabulation (optional). Identify the dependency direction in the recurrence. Allocate a table large enough to hold every reachable state. Fill it in an order that respects dependencies: every state read on the right-hand side must already be populated. The iteration order is determined by the dependency graph, not by mechanically reversing the recursion.
Optimize space (optional). Look at the recurrence. If dp[i] reads only dp[i-1] and dp[i-2], you do not need the full array; two variables suffice. If dp[i][j] reads only dp[i-1][...], drop the first dimension and use a 1D rolling array. For 1D knapsack-family problems, iteration direction matters: 0/1 needs right-to-left to avoid reusing items; unbounded needs left-to-right.

The optional steps are often skipped in interviews. A memoized recursion with the correct recurrence is usually enough to demonstrate understanding. Tabulation and space optimization come up as follow-up questions.

When DP Is Not The Answer

DP applies to a narrow set of structures. A few situations look DP-shaped but aren't:

Greedy works. Interval scheduling, MST (Kruskal/Prim), Huffman coding, and many activity-selection problems have provable greedy solutions. A correct greedy is faster than DP and has lower constants. Check whether the local choice ever needs revision; if it never does, greedy is sufficient.
State space is too large. TSP on n = 30 cities has 2^30 * 30 = 32 billion states, which is infeasible. Bitmask DP works up to n ≈ 20. Beyond that, the problem usually requires approximation, branch-and-bound, or a smarter formulation.
No optimal substructure. Longest simple path in a general graph (no repeated vertices) lacks optimal substructure: the longest simple path to a vertex v is not built from the longest simple path to a predecessor, because the predecessor's path might overlap with the extension. This problem is NP-hard, and DP does not help. Longest path on a DAG is fine because acyclicity removes the overlap risk.
The problem is online / streaming. DP assumes the input is fully available. If the input arrives one element at a time and you must commit to an answer before seeing the rest, the problem is online and requires different techniques (competitive analysis, online learning).
The answer is a structure, not a value. DP computes scalars and tables. If the question asks for "all paths" or "all valid configurations," the answer size is often exponential and you need backtracking with pruning, not DP. DP can count or characterize them, but not enumerate them efficiently.

One quick test: if the recurrence does not simplify to "look at a small constant number of smaller states," DP is probably the wrong shape. Either the state needs to grow or the problem needs a different approach.

The DP Variants of Dynamic Programming

DP problems are organized by the shape of the state and the recurrence. Each variant is a recipe for a recognizable problem family.

Variant	Shape	Canonical Problems
1D DP	`dp[i]` indexed by position in a sequence	Climbing Stairs, House Robber, Decode Ways, Longest Increasing Subsequence
2D Grid DP	`dp[i][j]` indexed by row and column	Unique Paths, Minimum Path Sum, Maximal Square, Dungeon Game
0/1 Knapsack	`dp[i][w]` over items and capacity, each item used at most once	Subset Sum, Partition Equal Subset Sum, Target Sum
Unbounded Knapsack	Same shape, but items can be reused	Coin Change, Coin Change II, Rod Cutting
State Machine DP	Multiple states per position; transitions defined by a state diagram	Best Time to Buy and Sell Stock variants, Paint House
String DP	`dp[i][j]` over two-string prefixes or substring boundaries	Edit Distance, LCS, Longest Palindromic Subsequence, Wildcard Matching
Bitmask DP	State is a subset of a small set (n ≤ 20)	Travelling Salesman, Partition to K Equal Sum Subsets, Set Cover
Digit DP	State is (position, tight flag, property accumulator) over the digits of a number	Count numbers with a property up to N, divisibility-based counting
Tree DP	State lives at a tree node; computed via post-order	House Robber III, Diameter of Binary Tree, Maximum Path Sum
Probability / Expectation DP	Stores a probability or expected value at each state	Knight Probability, New 21 Game, Soup Servings

These variants appear roughly in order of increasing state-design difficulty. 1D and 2D DP are mechanical once the state is fixed. Knapsack adds the item-versus-capacity trade-off and the iteration-direction subtlety. State machine introduces multiple per-position states. Bitmask, Digit, and Tree DP each introduce a different state representation that does not look like an array index.

The simplest variant to start with is 1D DP: state indexed by a single position, with the recurrence reading from a small number of recent cells. Climbing Stairs, House Robber, and Decode Ways are the canonical problems. Once those are familiar, the move to 2D, knapsack, and the other variants is a matter of growing the state, not learning new mechanics.

Quiz

Introduction to Dynamic Programming Quiz

10 quizzes

Introduction to Dynamic Programming (DP)