Dynamic programming explained: state, transition, base and three worked problems
Elman Huseynov · 2026-10-21 ·
Short answer. Dynamic programming solves a problem through the answers to its smaller versions. The answer for n is built from the answers for n - 1 and n - 2. Each small answer is computed once and stored. "How many ways", "minimum cost" and "maximum profit" problems then run in O(n) or O(n²).
What is dynamic programming?
Take a problem whose big answer is built from small ones. Define a state: what "the answer for i" means. Write a transition: how the answer for i follows from earlier answers.
The key condition is overlap. The small problems repeat. Plain recursion recomputes them again and again. Dynamic programming computes each one once.
The word "dynamic" means nothing here. The name is historical. The substance is a table of answers.
maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5])Find the largest sum of a contiguous stretch. The state at i is the best sum of a run that ends exactly at i.
Bars: how many times the answer for each stair i was computed, i from 0 to 18.
One operation is one call or one table cell. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
The pattern page: when to use it, and a template in six languages
When does a problem need dynamic programming?
- "In how many ways", "number of paths".
- "Minimum cost", "maximum sum with no two adjacent".
- "Can you make the amount from these coins", "can you split into two equal halves".
- "Longest increasing subsequence."
The shared signal: the whole answer depends on answers for its parts. And the parts are few. If each choice is independent of the past, greedy is enough. If you need every solution, that is backtracking.
What are the three steps of a dynamic programming solution?
- State. dp[i] is the answer for the first i elements, or for number i.
- Transition. A formula that expresses dp[i] through dp at smaller indexes.
- Base. The dp values for the smallest i, known up front.
Then comes the order. Compute from the base towards the target. Every transition must read cells that are already filled.
What does one problem look like?
Climbing Stairs: n steps, you climb one or two at a time. How many ways to reach the top?
State: dp[i] is the number of ways to reach step i. Transition: dp[i] = dp[i - 1] + dp[i - 2]. You arrive from i - 1 or from i - 2. Base: dp[1] = 1, dp[2] = 2.
For n = 5: dp = [_, 1, 2, 3, 5, 8]. Answer 8. Those are Fibonacci numbers, and that is no accident.
How do you write dynamic programming in Python?
def climb_stairs(n):
if n <= 2:
return n
a, b = 1, 2 # dp[i-2], dp[i-1]
for _ in range(3, n + 1):
a, b = b, a + b
return b
def coin_change(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount # dp[x] = fewest coins for amount x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return -1 if dp[amount] == INF else dp[amount]
def rob(houses):
take = skip = 0 # best with last house taken / skipped
for h in houses:
take, skip = skip + h, max(take, skip)
return max(take, skip)The first function keeps two variables instead of an array. When the transition looks back two steps, the array is not needed.
Bottom-up or top-down: which one to write?
| Trait | Bottom-up (table) | Top-down (memoisation) |
|---|---|---|
| Code shape | A loop | Recursion with a cache |
| Order | You choose it | Recursion chooses it |
| Memory | Often shrinks to O(1) | Cache plus call stack |
| Wasted work | Sometimes every state | Only states you need |
| Risk | Wrong order | Stack overflow |
In an interview, start with recursion and a cache. The transition is easier to find that way. Rewrite as a loop if asked.
How does dynamic programming solve Coin Change?
You get coin values and an amount. Return the fewest coins. State: dp[x] is the fewest coins for amount x. Transition: for each coin c, try dp[x - c] + 1. Base: dp[0] = 0.
Greedy fails here. Coins [1, 3, 4], amount 6. Greedy picks 4 + 1 + 1. The answer is 3 + 3. That failure is why the table is needed.
How does it solve House Robber?
A row of houses with money. You cannot rob two neighbours. Maximise the total.
State: the best result for the first i houses. Transition: rob house i and add the best for i - 2. Or skip it and keep the best for i - 1. The code above holds that in take and skip.
What mistakes break a dynamic programming solution?
- A vague state. The transition then cannot be written in terms of it.
- A missing or wrong base. The error spreads through the whole table.
- An order where a transition reads an empty cell.
- Going greedy where the states have to be searched.
How do you explain dynamic programming in an interview?
Say the state out loud in one sentence. Then the transition. Then the base. Only then write code. The interviewer is listening for those three sentences.
Give the complexity as states times transition cost. For Coin Change that is O(amount · coins).
Drill this pattern on the dynamic programming page. The top-down form lives on the recursion with memoization page.
FAQ
How do you know a problem is not greedy?
Find an input where the best local choice hurts the total. Coins [1, 3, 4] with amount 6 is one. Found one: you need the table.
How many states are acceptable?
Up to a few million, usually. More than that: look for a different parameter or a different pattern.
What if you need the actual answer, not just a number?
Store the choice that produced dp[i] next to it. At the end, walk the choices backwards and rebuild the answer.
Where does dynamic programming show up in real systems?
DNA alignment and spell checking through edit distance. Data compression and line breaking in text layout. Routing that finds the cheapest path in stages.