Skip to content

Volume ITechnology

4.23.1 — Climbing Stairs ​

LeetCode 70 · Easy · ★ Blind 75

The problem ​

You climb a staircase of n steps, taking 1 or 2 steps at a time. How many distinct ways are there to reach the top?

n = 2  →  2     (1+1, or 2)
n = 3  →  3     (1+1+1, 1+2, 2+1)

The pattern ​

Ask the question backwards: how did you arrive at step n?

There are only two possibilities. You came from step n − 1 with a single step, or from step n − 2 with a double step. Those two groups do not overlap and cover everything, so:

\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2)

That is Fibonacci. The base cases are ways(1) = 1 and ways(2) = 2.

"How did I get here" is the question that produces almost every 1-D DP recurrence. Ask it before writing anything.

The brute force, and where it wastes work ​

Write the recurrence straight down as recursion, with no memory.

python
def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

It is correct, but painfully slow. climbStairs(5) calls climbStairs(4) and climbStairs(3). But climbStairs(4) also calls climbStairs(3). So climbStairs(3) is worked out twice, climbStairs(2) three times, and the repeats double with each step down. The number of calls grows roughly like 1.6^n. For n = 45, that is over a billion calls.

The waste in one sentence: the same smaller question is answered again and again, when answering each one once and remembering it would do.

Remembering each answer is the whole idea of dynamic programming: break a problem into smaller versions of itself, solve each smaller version once, and build the big answer from the stored small answers.

The four forms, on one problem ​

This problem is small enough to show all four forms from 4.22 side by side. Every other DP problem is one of these shapes with a harder recurrence.

Form 1 — memoised recursion.

python
def climbStairs(self, n: int) -> int:
    from functools import lru_cache

    @lru_cache(None)
    def ways(step: int) -> int:
        if step <= 2:
            return step
        return ways(step - 1) + ways(step - 2)

    return ways(n)

Write the plain recursion, then add a cache. O(n) time and space, plus the call stack. lru_cache is Python's built-in memoisation decorator, and you will use it often.

Form 2 — full table.

python
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]

The recursion's parameter became the array index. The loop goes upwards because dp[i] reads smaller indices.

Forms 3 and 4 — two variables. Since dp[i] only reads the previous two cells, the array is unnecessary.

python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:  # (1)
            return n

        prev, curr = 1, 2                    # (2) ways(1), ways(2)
        for _ in range(3, n + 1):  # (3)
            prev, curr = curr, prev + curr  # (4)

        return curr  # (5)
ts
function climbStairs(n: number): number {
  if (n <= 2) return n;  // (1)

  let prev = 1, curr = 2;  // (2)
  for (let i = 3; i <= n; i++) {  // (3)
    [prev, curr] = [curr, prev + curr];  // (4)
  }

  return curr;  // (5)
}

O(n) time, O(1) space.

Line by line ​

(1) The base cases. One step can be climbed one way. Two steps can be climbed two ways: 1 + 1, or 2. Returning n covers both.

(2) prev is the number of ways to reach the step two below the current one, and curr the number of ways to reach the step just below. At the start, they are the answers for steps 1 and 2.

(3) Work upward, from step 3 to step n.

(4) Slide both values up by one step. The new curr is prev + curr: the ways to reach this step are the ways to reach the step one below plus the ways to reach the step two below. The old curr becomes the new prev.

(5) After the loop, curr holds the answer for step n.

Trace ​

For n = 5:

Stepprev (2 below)curr (1 below)New curr = sum
start12—
3231 + 2 = 3
4352 + 3 = 5
5583 + 5 = 8

The answer is 8. Check it by hand: the ways to climb 5 steps are 1+1+1+1+1, four orders of one 2 and three 1s, and three orders of two 2s and one 1. That is 1 + 4 + 3 = 8.

The simultaneous assignment matters. prev, curr = curr, prev + curr evaluates the whole right-hand side first. Writing it as two statements would overwrite prev before prev + curr is computed. In JavaScript the destructuring assignment does the same job; without it you need a temporary.

Complexity ​

O(n) time, O(1) space.

There is also an O(\log n) solution using matrix exponentiation on the Fibonacci recurrence, and a closed form using the golden ratio — which loses precision for large n. Worth naming; not worth writing.

Edge cases ​

  • n = 1. One way. Line (1) returns 1.
  • n = 2. Two ways. Line (1) returns 2.
  • Large n, up to 45 here. The answer grows quickly, about 1.6 times per step, but it still fits in an ordinary number. Python whole numbers never overflow at all.

Why this problem is worth more than it looks ​

It is the smallest possible complete DP, so it is the one to use when you are deriving the method rather than the answer. If you can produce all four forms for this, the machinery is in place and every harder problem is just a harder recurrence.

And it establishes the counting rule: ways to reach a state = sum of the ways to reach every state that leads to it. Counting problems add; optimisation problems take a minimum or maximum. Which operator you use is the only difference between "how many ways" and "the cheapest way".

Where this goes next ​

  • Min Cost Climbing Stairs — same two moves, but minimising a cost instead of counting. + becomes min. 4.23.2.
  • Climbing with steps of 1, 2 or 3 — three terms instead of two.
  • Climbing with an arbitrary step set — sum over every allowed step size, which is Combination Sum IV, and the same recurrence.
  • Decode Ways — the same "one or two at a time" structure, with validity conditions attached. 4.23.7.
  • Unique Paths — the two-dimensional version: arrive from the left or from above. 4.24.1.

What the interviewer will push on ​

"Derive the recurrence." Ask how you arrived at step n. Two disjoint cases that cover everything.

"What are the base cases?" ways(1) = 1, ways(2) = 2. Check them by hand; a great many wrong DP solutions are correct recurrences with wrong bases.

"Can you do it in O(1) space?" Two variables.

"What if you could take up to k steps?" Sum the previous k values. A sliding window sum keeps it O(n) rather than O(nk).

"Can you do better than O(n)?" Matrix exponentiation, O(\log n).

One thing to volunteer: say "this is Fibonacci" as soon as you have the recurrence. Recognising a known sequence is faster and more convincing than deriving the code.

Next: 4.23.2 Min Cost Climbing Stairs — the same two moves, optimising instead of counting.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet