Explore 1-D dynamic programming interview patterns: climbing stairs, house robber, coin change, word break and more. Watch the table fill and study Python solutions.
The pattern
1-D Dynamic Programming: solve each smaller problem once
Dynamic programming is recursion that remembers. When the answer for a big input is built from answers for smaller ones, and the same smaller ones keep coming up, store each answer in a table the first time. In these problems the table is a single row, indexed by position, amount or length.
1The same question, asked again and again
Plain recursion for climbing stairs solves f(3) twice and f(2) three times, and it gets exponentially worse. Dynamic programming answers each smaller question once and remembers it.
2Fill a table in order
Write the answer for each smaller input in an array, in an order where everything an entry needs is already filled. Then each entry is a line of arithmetic on earlier ones.
3Find the last decision
Most recurrences come from the last choice: the last step taken, rob this house or skip it, the last coin used. Each option points to a smaller problem you've already solved.
How to build the recurrence
- Define dp[i] in words first: “the most money from the first i houses”, “ways to decode s[i:]”.
- Look at the last choice and write dp[i] from smaller entries (sum for counting, min or max for optimising).
- Base cases and a fill order where every entry's needs are ready.
- Shrink the memory if an entry only needs the last one or two.
Reading the pictures
- The table is the bottom row. Teal is the entry being filled; amber are the entries it's built from; green are filled.
- The brute force on the right is the plain recursion: watch how many calls it needs compared with the table.
- For more DP with a grid, see the Dynamic Programming visualizer.
NeetCode 150 · 1-D Dynamic Programming
All 12 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Climbing Stairs
EasyBlind 75You're climbing a staircase of n steps, taking 1 or 2 steps at a time. In how many distinct ways can you reach the top?
n = 5
ways[i] = number of ways to reach step i
variables
- n
- 5
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 6 ops
- Brute force
- 15 ops
On a bigger input (n = 25):
- Pattern
- 26 ops
- Brute force
- 242,785 ops
Plain recursion, ways(n) = ways(n − 1) + ways(n − 2), with no memory: the same smaller cases are solved over and over, and the number of calls grows like 1.6^n.
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Climbing Stairs
Step by step
- Entry being filled
- Entries it's built from
- Filled
Press Start or Step: the step the animation is on lights up below.
- 1
ways(i) = ways(i − 1) + ways(i − 2)
one, two = 1, 1 - 2
Base cases
ways(0) = ways(1) = 1 - 3
Fill the next entry from the two before
for i in range(n - 1): one, two = one + two, one - 4
ways(n)
return one
Look at the last move. To reach step i you came from i − 1 (one step) or i − 2 (two steps), so ways(i) = ways(i − 1) + ways(i − 2), with ways(0) = ways(1) = 1.
Recursion repeats work; a table filled from the bottom computes each value once. Each entry only needs the previous two, so two variables are enough (NeetCode's one, two).
Spot it in an interview
- Count the ways to reach a state when each move comes from a few earlier states: add up their counts.
- The first DP problem: spot the recurrence from the last decision.
One addition per step, keeping only the last two values.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.