Dynamic programming, or DP, is a technique for solving a problem by breaking it into smaller subproblems, solving each subproblem once, and reusing that answer every time it is needed again instead of recomputing it. That is the whole idea. The reputation for difficulty comes from a different skill: recognizing when a problem qualifies, and designing the right state to cache. Get those two things right and the caching part is almost mechanical.
What changed in 2026
- The core technique is unchanged — DP has been formalized since the 1950s — but recognizing DP-shaped problems remains one of the most-tested skills in technical interviews, arguably weighted more heavily than raw implementation speed.
- AI coding assistants got good at writing DP solutions once the state is specified, which shifted the actual bottleneck even further toward correctly identifying the subproblem and state, not the mechanical code.
- DP-adjacent techniques, such as memoized graph search and DP over trees, appear more often in real infrastructure code — cost-based query planners and compiler optimizers use DP-style subproblem caching directly.
The two-question test
A problem is a DP candidate only if both are true:
- Optimal substructure: the best overall solution can be built from the best solutions to its subproblems. If solving each piece optimally does not guarantee an optimal whole, DP does not apply cleanly.
- Overlapping subproblems: the same subproblem gets solved more than once under plain recursion. If every subproblem is distinct, there is nothing to cache — that usually signals a divide-and-conquer problem instead, like merge sort, not a DP one.
If only the first is true, a greedy algorithm may be a better fit instead — greedy also builds a solution from optimal pieces, but never revisits a choice and never needs a cache.
A worked example: climbing stairs
The problem: climbing 1 or 2 steps at a time, how many distinct ways are there to reach step n?
Plain recursion re-solves the same subproblem repeatedly:
ways(n):
if n <= 1: return 1
return ways(n-1) + ways(n-2) # ways(n-2) gets recomputed many times over
ways(5) calls ways(3) twice and ways(2) three times — that duplication is the overlapping-subproblems signal. Caching each result the first time it is computed turns exponential recursion into linear work:
ways(n):
cache = {0: 1, 1: 1}
for i in 2..n:
cache[i] = cache[i-1] + cache[i-2]
return cache[n]
This is DP end to end: identify the subproblem, ways(k) for each step count, confirm it repeats, cache it, and build the answer from smaller cached answers.
Two ways to apply the cache
| Approach |
How it works |
Tradeoff |
| Top-down, memoization |
Write the natural recursion, cache each result the first time |
Easier to derive from the recursive definition |
| Bottom-up, tabulation |
Fill a table from the smallest subproblem upward, no recursion |
Usually faster, no call overhead, but needs the fill order figured out upfront |
Both produce the same answer and the same complexity class. Starting with top-down works well when the recursive definition comes naturally; converting to bottom-up once it works is the move when performance matters.
How DP relates to other techniques
- Vs plain recursion: identical subproblems, but plain recursion recomputes; DP caches. The recurrence is the same in both.
- Vs greedy algorithms: greedy commits to one locally-best choice per step and never looks back; DP considers the outcomes of multiple choices and picks the best, which is why DP handles problems, like 0/1 knapsack, that break greedy.
- Vs backtracking: backtracking explores every valid path and abandons dead ends; DP short-circuits that exploration by reusing cached subproblem answers instead of re-deriving them.
Common pitfalls
Applying DP to independent subproblems. If subproblems never repeat, caching adds memory overhead for zero benefit — plain divide-and-conquer, like merge sort, is the better fit.
Getting the state definition wrong. A state missing information collapses distinct subproblems into one cache entry incorrectly; a state with too much information never reuses anything. This is the actual hard part of DP, not the caching mechanism itself.
Jumping straight to code before finding the recurrence. Writing the recurrence relation in words or math first — the answer for n depends on the answer for n-1 and n-2, in this way — before writing any cache or loop saves far more debugging time than it costs.
FAQ
Is dynamic programming just recursion with caching?
For the top-down form, essentially yes — the recursion is identical to the naive version, with a cache check added at the top and a cache write added before returning.
How can a problem be recognized as needing dynamic programming?
Try writing the brute-force recursive solution first. If the same function call happens with the same arguments more than once, it is a DP candidate.
What is the difference between dynamic programming and backtracking?
Backtracking explores and discards; dynamic programming reuses. Some problems, like generating all valid Sudoku solutions, genuinely need backtracking because every path is required, not just an optimal count or value.
Where to go next