Climbing Stairs (LeetCode 70): A Tiny Fibonacci in Disguise. A line‑by‑line walkthrough of a 4‑line Python solution, intuition, correctness, and faster alternatives.
Table of Contents
TL;DR
The number of distinct ways to climb n steps when you can take 1 or 2 at a time follows the Fibonacci numbers. A 4‑line, O(n) time and O(1) space solution uses two variables to iterate the sequence.
def climbStairs(n: int) -> int:
a, b = 1, 1 # f(0), f(1)
for _ in range(n):
a, b = b, a + b
return a
- Intuition: To reach step
n, you last came from stepn-1(take 1 step) or from stepn-2(take 2 steps):f(n) = f(n-1) + f(n-2). - Complexity: O(n) time, O(1) space.
Problem
Each time you can climb either 1 or 2 steps. How many distinct ways to reach the top of a staircase with
nsteps?
Constraints: 1 ≤ n ≤ 45.
Intuition: Why Fibonacci?
Let f(n) be the number of ways to stand on step n.
- If your last move was 1 step, you came from
n-1(there aref(n-1)ways to be there). - If your last move was 2 steps, you came from
n-2(there aref(n-2)ways to be there).
These are disjoint cases, so:
f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)
Base values:
f(0) = 1(one way to be at the ground: do nothing).f(1) = 1(one way: a single 1‑step).
This is exactly the Fibonacci recurrence with the shifted base. For the more common Fibonacci definition F(0)=0, F(1)=1, we have f(n) = F(n+1).
Line‑by‑Line Explanation (Python)
def climbStairs(n: int) -> int:
Defines a function that returns the count for a non‑negative integer n.
a, b = 1, 1 # f(0), f(1)
Initializes two rolling variables:
awill representf(k)andbwill representf(k+1)for the current iterationk.- Start with
k=0:a=f(0)=1,b=f(1)=1.
for _ in range(n):
Iterate exactly n times. After i iterations, the invariant will be: a=f(i), b=f(i+1).
a, b = b, a + b
One atomic parallel assignment (Python evaluates the right side first):
- New
abecomes oldb→ shifts us fromf(k)tof(k+1). - New
bbecomes olda + b→ computesf(k+2) = f(k+1) + f(k).
This advances both variables one step along the Fibonacci sequence without extra memory.
return a
After n iterations, a = f(n) — the number of distinct ways to climb n steps.
Dry‑Run Example (n = 4)
Start: a=1 (f(0)), b=1 (f(1))
| Iteration | a (f(k)) | b (f(k+1)) |
|---|---|---|
| 0 (init) | 1 | 1 |
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 3 | 5 |
| 4 | 5 | 8 |
Return a = 5 → there are 5 distinct ways for n=4.
Correctness Argument (Loop Invariant)
Invariant: Before each iteration k (starting at 0), a = f(k) and b = f(k+1).
- Initialization: At
k=0,a=1=f(0),b=1=f(1). - Maintenance: The update
a, b = b, a + bmakes newa = f(k+1)and newb = f(k) + f(k+1) = f(k+2). - Termination: After
niterations,a = f(n).
Thus, return a is correct.
Complexity
- Time: O(n) — one pass with constant work per iteration.
- Space: O(1) — only two integers are kept, regardless of
n.
Note: For the given constraint n ≤ 45, integer sizes are tiny; overflow is not a concern in Python (arbitrary precision) or 32‑bit signed ints (max result for n=45 is 1,836,311,903).
Alternatives & Optimizations
1) Fast Doubling (O(log n) time, O(1) space)
A numerically stable method that computes Fibonacci numbers using divide‑and‑conquer identities:
F(2k) = F(k) * [2*F(k+1) − F(k)]F(2k+1) = F(k+1)^2 + F(k)^2
We return F(n+1) for f(n).
def climbStairs_fast(n: int) -> int:
# returns (F(n), F(n+1)) with F(0)=0, F(1)=1
def fib_pair(m: int):
if m == 0:
return (0, 1)
a, b = fib_pair(m // 2)
c = a * (2 * b - a)
d = a * a + b * b
if m % 2 == 0:
return (c, d)
else:
return (d, c + d)
return fib_pair(n + 1)[0] # F(n+1) = f(n)
2) Combinatorics (Closed Form Sum)
Choosing where the 2‑steps go among (n−k) moves total when you take k double steps:
f(n)=∑k=0⌊n/2⌋(n−kk)f(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}
Elegant for math insights, but slower to compute directly for large n.
3) Classic DP Array (O(n) time, O(n) space)
Clear but uses extra memory:
def climbStairs_dp(n: int) -> int:
f = [0] * (n + 2)
f[0], f[1] = 1, 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]
Edge Cases & Pitfalls
- n = 1: Returns 1 (only one 1‑step).
- n = 2: Returns 2 (1+1, 2).
- Off‑by‑one mistakes: If you start with
(a, b) = (0, 1)you must returnbat the end; with(1, 1)you returna. - Do not build all paths: The count grows exponentially; enumerating paths is unnecessary and expensive.
Testing (pytest)
import pytest
from typing import Callable
SOLS: list[Callable[[int], int]] = []
# drop your implementations here
def climbStairs(n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
SOLS.append(climbStairs)
def climbStairs_fast(n: int) -> int:
def fib_pair(m: int):
if m == 0:
return (0, 1)
a, b = fib_pair(m // 2)
c = a * (2 * b - a)
d = a * a + b * b
return (c, d) if m % 2 == 0 else (d, c + d)
return fib_pair(n + 1)[0]
SOLS.append(climbStairs_fast)
@pytest.mark.parametrize("n, expected", [
(1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89), (45, 1836311903)
])
def test_climb_stairs(n, expected):
for f in SOLS:
assert f(n) == expected
Variations You’ll See in Interviews
- Different step sets: Allowed steps are
{1, 3, 5}or any setS. Usedp[i] = sum(dp[i-s] for s in S if i-s >= 0). - Exactly k steps: Count ways to use exactly
kmoves — use combinatorics or 2D DP. - Min cost to reach the top: Each step has a cost; compute min cost with DP (
min(dp[i-1], dp[i-2]) + cost[i]).
Takeaways
- The staircase problem is Fibonacci in disguise.
- A simple two‑variable loop gives optimal space and clear correctness.
- Fast doubling offers a clean O(log n) upgrade when
nis large.
About Connect Kreations
At Connect Kreations, we bridge the gap between technology and the community — simplifying complex ideas with practical code and hands‑on learning. If you found this useful, share it with a fellow learner and explore more guides on algorithms and interview prep.
Tags: algorithms, dynamic programming, fibonacci, interview‑prep, python, leetcode-70
