~20 minutes · Day 61 · dynamic programming · Python
Tonight's problem is Climbing Stairs. It looks tiny: you can climb 1 or 2 steps at a time, and you need the number of ways to reach the top. In interviews, this is the cleanest first test of dynamic programming: can you name the repeated question, answer it once, and reuse it?
Every DP is four answers: what dp[i] means, how it comes from smaller states, the base case, and where the final answer lives. Here: ways(i) = ways(i-1) + ways(i-2).
That line is the whole lesson. Dynamic programming is useful when the same smaller questions appear again and again; the standard move is to store those answers instead of recomputing them (Wikipedia: dynamic programming).
If ways(i) means "ways to reach step i", then the last jump into i was either from i - 1 or from i - 2. A direct recursive version says exactly that:
def ways(i):
if i == 0 or i == 1:
return 1
return ways(i - 1) + ways(i - 2)
This is correct, but slow: the recursion tree repeats the same calls many times, following the same recurrence shape as the Fibonacci sequence. The fix is not a clever trick. It is the four questions, written down in order.
The diagram is the interview explanation. Each cell is one answered question. To fill dp[i], you do not look into the future; you only use smaller states already filled.
Python lists store values by index, which is exactly what this table needs (Python docs: data structures). LeetCode gives n >= 1, so the two base cells below are always valid.
def climb_stairs(n):
dp = [0] * (n + 1) # dp[i] means ways to reach step i
dp[0] = 1 # one way to stand at the ground
dp[1] = 1 # one way to reach the first step
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # arrive by a 1-step or 2-step jump
return dp[n] # final answer lives at the top
Read that code through the four questions: state, transition, base case, answer location. If any one of those is blurry, the bug usually appears there.
Min Cost Climbing Stairs asks for the cheapest cost instead of the number of ways. Before opening the reveal, predict the four answers: what does dp[i] mean, what smaller states can reach it, what are the base cases, and where is the answer?
The state becomes "minimum cost to stand on step i." The transition changes from sum to minimum: dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]). Same DP habit, different verb.
| Approach | Time | Space |
|---|---|---|
| Brute force recursion | O(2^n) | O(n) |
| DP table | O(n) | O(n) |
| DP with two variables | O(n) | O(1) |
The table version is the best first version because it makes the four answers visible. After that, you can compress space because only the previous two cells are needed.
1. In Climbing Stairs, what does dp[i] mean?
dp[i] is the count of ways to reach exactly step i. Once that state is clear, the transition almost writes itself.2. Which transition fills the current cell?
i came from i - 1 or i - 2, so those two counts combine.3. Spot the bug in this DP setup:
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]dp[0] should be 1: there is one way to be at the ground before any jump. That base case feeds every later answer.4. Which is not one of the four DP questions?
Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
For the encode step, write the invariant at the top of this page in your own words, then add the exact transition: ways(i) = ways(i - 1) + ways(i - 2).
Watch NeetCode — Climbing Stairs after your attempt, as the compare step. Find the exact sentence where his recurrence explanation becomes clearer than yours.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.