LeetMotion
You are given an integer n representing the number of steps to reach the top of a staircase. You can climb with either 1 or 2 steps at a time. Return the number of distinct ways to climb to the top.
1 ≤ n ≤ 45Stand at step i. How did you get here? Either you came from step i − 1 (with a 1-step jump) or from step i − 2 (with a 2-step jump). There are no other options. So:
This is exactly the Fibonacci recurrence. Base cases: ways(1) = 1 (only one path: [1]) and ways(2) = 2 (paths: [1,1] or [2]). The recursion tree has overlapping subproblems — ways(3) is computed twice when computing ways(5) naively. That's the signal to use DP.
Try all paths: from step i, recurse into dfs(i+1) and dfs(i+2). Return 1 when i == n (exact hit), 0 when i > n (overshot). Simple but exponential — the same subproblems are recomputed exponentially many times.
def climbStairs(self, n: int) -> int:
def dfs(i):
if i == n: return 1 # reached top exactly
if i > n: return 0 # overshot
return dfs(i + 1) + dfs(i + 2)
return dfs(0)Same recursion but cache every dfs(i) result. The first time we compute it, we store it; on repeat visits we return the cached value instantly. Reduces from exponential to linear by eliminating redundant recomputation.
def climbStairs(self, n: int) -> int:
cache = [-1] * (n + 2)
def dfs(i):
if i == n: return 1
if i > n: return 0
if cache[i] != -1: return cache[i]
cache[i] = dfs(i + 1) + dfs(i + 2)
return cache[i]
return dfs(0)Flip the recursion around: build the answer iteratively from the base cases upward. Fill dp[1]=1, dp[2]=2, then for i from 3 to n, compute dp[i] = dp[i-1] + dp[i-2]. No stack overhead, no cache misses — just a simple loop.
def climbStairs(self, n: int) -> int:
if n <= 2: return n
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]Since dp[i] only uses dp[i-1] and dp[i-2], we don't need the entire array — just two variables. Slide them forward each iteration. This is computing Fibonacci numbers in O(1) extra space.
def climbStairs(self, n: int) -> int:
one, two = 1, 1 # one = curr, two = prev
for i in range(n - 1):
temp = one
one = one + two
two = temp
return oneThe Fibonacci matrix identity [F(n+1), F(n); F(n), F(n-1)] = [[1,1],[1,0]]^n lets us compute the answer in O(log n) via fast matrix power (binary exponentiation). Overkill for n ≤ 45 but demonstrates the technique.
def climbStairs(self, n: int) -> int:
def mat_mul(A, B):
return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
[A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]]
def mat_pow(M, p):
res = [[1,0],[0,1]]
while p:
if p & 1: res = mat_mul(res, M)
M = mat_mul(M, M); p >>= 1
return res
return mat_pow([[1,1],[1,0]], n)[0][0]The nth Fibonacci number has a closed-form solution using the golden ratio φ = (1+√5)/2. Since climbing stairs = Fibonacci, we compute it directly with one formula. Floating-point precision requires rounding.
import math
def climbStairs(self, n: int) -> int:
sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
psi = (1 - sqrt5) / 2
return round((phi**(n+1) - psi**(n+1)) / sqrt5)| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion | O(2ⁿ) | O(n) | Stack depth n, exponential calls |
| Memoization | O(n) | O(n) | Each subproblem computed once |
| Bottom-Up DP | O(n) | O(n) | No recursion overhead |
| Space-Optimized | O(n) | O(1) | Interview favourite ✓ |
| Matrix Exp | O(log n) | O(1) | Generalises to any linear recurrence |
| Binet's Formula | O(log n) | O(1) | Floating-point risk for large n |
Climbing stairs is the canonical 1-D DP problem. Recognise it by:
i depends on a fixed number of prior states (here: 2).Every path to step i ends with either a 1-step jump from i-1 or a 2-step jump from i-2. These two sets of paths are disjoint (they don't share their last move). So the total count is their sum — no double-counting, no missing paths.
If you can jump 1 to k steps, the recurrence becomes dp[i] = dp[i-1] + dp[i-2] + … + dp[i-k]. The DP still runs in O(n·k). This is called the tribonacci extension for k=3, and so on.
The most common bug: initialising dp[0] instead of starting from dp[1] and dp[2], or starting the loop from i=1 which overwrites base cases.
# WRONG — loop starts too early, overwrites dp[1] and dp[2]
for i in range(1, n + 1):
dp[i] = dp[i-1] + dp[i-2]
# CORRECT — preserve base cases
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]If you access dp[2] before checking n < 2, you'll get an index-out-of-bounds for n=1. Always guard with if n <= 2: return n.
After the swap, one holds ways for the current step and two holds the previous. Getting this backwards gives the wrong Fibonacci offset. Trace through n=3 by hand: one=1,two=1 → one=2,two=1 → return 2. Correct: ways(3)=3 is returned after the loop runs twice (n-1=2 iterations). Check your iteration count.
n=1 → 1 (only [1])n=2 → 2 ([1,1] or [2])n=3 → 3 ([1,1,1], [1,2], [2,1])n=4 → 5 (Fibonacci confirms: 1,2,3,5)n=5 → 8
Discussion
…