Dynamic programming: how to spot it
We'll cover the following
Solve a small version, write the answer down, and build the next one from it. When the same sub-problem keeps repeating, you only need to solve it once.
How the question sounds
- Maximum, minimum, fewest, or number of ways
- Each choice depends on a few earlier answers, like climb 1 or 2 steps
- Maximum contiguous subarray sum (Kadane)
- Take or skip each item
- Brute force tries every combination and the same sub-problems repeat
The two shapes
Where it shows up in GenAI work
Edit distance and sequence alignment drive evaluation metrics and diffing. Dynamic programming also appears in Viterbi-style decoding and in cost-optimal batching.
Is it dynamic programming?
Decide yes or no before you open each answer.
Check yourselfFind the maximum sum of a contiguous subarray.
Yes. Kadane's: extend the previous run or restart. A tiny DP.
Check yourselfIn how many distinct ways can you climb n stairs taking 1 or 2 steps?
Yes. ways(n) = ways(n-1) + ways(n-2).
Check yourselfWhat is the fewest coins that make an amount?
Yes. best(a) = 1 + min(best(a - coin)). Sub-problems overlap.
Check yourselfFind a target in a sorted array.
No. Binary search.
Check yourselfFind the shortest path in an unweighted maze.
No. BFS spreads out evenly and finds it first.
Check yourselfFind two numbers in an unsorted array that sum to a target.
No. Hash map lookup.
Problems in this pattern
- Climbing stairs · Easy · Build from last two
- House robber · Medium · Take or skip
- Maximum subarray (Kadane) · Medium · Extend or restart
- Coin change · Medium · Table of amounts
Summary: say it in the interview
- Build up: Fill a table from the smallest case upward. Each cell comes from cells you already filled.
- Choose each step: At each item decide between two options, like take or skip, extend or restart, and keep the better one.