Dynamic Programming: how to recognize it in 60 seconds
Most people fail DP problems before writing a line because they do not spot the pattern. Here is a fast recognition checklist and the path from recurrence to working code.
Dynamic programming has a reputation for being hard. The truth is narrower: recognizing a DP problem is hard, and once you have recognized it, the mechanical part is almost a recipe. If you can spot the pattern in the first minute, you have already won most of the battle.
The 60 second recognition test
Ask yourself three questions. If you answer yes to all three, it is dynamic programming.
- Are you optimizing or counting? Words like maximum, minimum, longest, fewest, or number of ways are loud signals.
- Do choices chain? A decision now constrains decisions later. You take or skip an item, and that changes what is left.
- Do subproblems repeat? If a naive recursion would re-solve the same state many times, you have overlapping subproblems, and memoizing them is the whole trick.
The two formal properties underneath are optimal substructure, the best answer is built from best answers to subproblems, and overlapping subproblems, those subproblems recur. Greedy needs the first but not the second. DP needs both.
From recognition to a recurrence
Once you know it is DP, the work is defining the state. State is the smallest set of variables that fully describes a subproblem.
- For the coin change minimum, state is the remaining amount.
- For the longest common subsequence, state is the pair of indices into the two strings.
- For the knapsack, state is the item index and the remaining capacity.
Write the recurrence as plain English first: the answer at this state equals the best over the choices I can make, plus the cost of that choice. Translate that sentence into code and you have a top down solution.
from functools import lru_cache
@lru_cache(None)
def best(amount):
if amount == 0:
return 0
if amount < 0:
return float('inf')
return min(best(amount - c) + 1 for c in coins)
That is coin change. The decorator memoizes every state so each is computed once. The runtime is the number of states times the work per state, which is the formula you cite when asked for complexity.
Top down or bottom up
Memoized recursion, top down, is the fastest to write and the easiest to reason about. Start there. Convert to a bottom up table only when you need to, usually to shave the recursion stack or to compress space to one rolling row.
A practical tip: if you can write the top down version, you have proven the recurrence is correct. The bottom up rewrite is then a purely mechanical reordering, not a fresh problem.
The traps
- State too big. If your state has five variables, you probably included something you can derive. Smaller state means a smaller table.
- Forgetting base cases. Half of wrong DP answers come from an unhandled empty or zero case.
- Greedy in disguise. Some optimize-or-count problems are actually greedy or interval based. Sorting plus a sweep, like merge intervals, can beat a heavy DP table. Recognize the difference before you commit.
Build the reflex
DP recognition is a trained instinct, not a formula you memorize. The only way there is volume. Work the Algorithms track and let a roadmap feed you DP variants in a sensible order rather than throwing the hardest ones at you cold. If you want the broader foundations, the full Learn library covers the supporting structures.
Beat the machine
The sixty second test only works if you have seen enough problems for the pattern to fire automatically. Jump into the arena and solve DP problems against an AI matched to your tier. Train the instinct under real pressure and find out whether you can still beat the machine.