Climbing Stairs: Where Dynamic Programming Starts

If you interview at Amazon, Google, Adobe, expect some version of "Climbing Stairs". It is rated Easy, and it falls squarely into the Dynamic Programming pattern — pattern-first preparation beats grinding random problems every time. Part 1 of 11 in the Dynamic Programming arc.

The Problem

You climb a staircase of n steps taking 1 or 2 steps at a time; how many distinct ways reach the top? The hello-world of DP — asked not for difficulty but to watch your method: state, recurrence, base cases, then code.

Input:  n = 3
Output: 3
1+1+1, 1+2, 2+1.

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Count the ways with local choices and no relevant history beyond position — the final hop was 1 or 2, so ways(n) = ways(n−1) + ways(n−2), Fibonacci exactly. Counting problems whose last decision splits into disjoint cases are the smallest DP shape.

The Approach

State the recurrence and bases (ways(1) = 1, ways(2) = 2) before any code — that narration is the assessment. Then observe only two previous values are ever live, collapse the table to two variables, and note the space drop from O(n) to O(1).

Naive recursion is exponential from recomputing shared subtrees — say it with the tree picture in one sentence, because the fix-the-recomputation story is the entire pattern in miniature.

Python Solution

def climb_stairs(n: int) -> int:
    """Distinct 1-or-2-step ways to climb n stairs."""
    if n <= 2:
        return n
    prev2, prev1 = 1, 2                # ways(1), ways(2)
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Complexity

• Time: O(n) — one loop iteration per step
• Space: O(1) — two rolling variables replace the table

Interview Tips and Follow-Ups

• Escalations arrive fast: steps from a set (Coin Change combinations), forbidden stairs (zero out states), cost per stair (Min Cost Climbing) — same recurrence family.
• Matrix exponentiation gives O(log n) — a flex worth one sentence at Google, no more.
• Practice the narration order — state, recurrence, bases, then code — until it is automatic; interviewers grade the order itself on DP questions.

If this clicked, continue the Dynamic Programming arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.