Easy#706 min readDynamic Programming1D DPLeetCode

Climbing Stairs

Fibonacci recurrence

Fibonacci in disguise. dp[i] = dp[i-1] + dp[i-2]. Start here.

Published Apr 15, 2026

Problem

You are climbing a staircase with n steps. Each move, you can climb either 1 or 2 steps. How many distinct ways can you reach the top?

Input

n = 2

Output

Explanation

(1+1) or (2)

Input

n = 5

Output

Intuition

Stand on step n. How did you get here? Either you took a 1-step from n - 1, or a 2-step from n - 2. So:

ways(n) = ways(n - 1) + ways(n - 2)

That's Fibonacci. The problem is Fibonacci in disguise — and once you see that, the entire DP hierarchy opens up. Every DP problem has this shape: the answer at state n is a function of the answers at "nearby" states.

Approach

Memoized Recursion

TimeO(n)

SpaceO(n)

Naïve recursion recomputes the same subproblems exponentially. Adding a memo table makes each state computed once. Good for understanding — worse in practice because of function-call overhead and stack depth.

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        fn ways(n: i32, memo: &mut Vec<i32>) -> i32 {
            if n <= 2 {
                return n;
            }
            if memo[n as usize] = 0 {
                return memo[n as usize];
            }
            let r= ways(n - 1, memo) + ways(n - 2, memo);
            memo[n as usize]= r;
            r
        }
        let mut memo= vec![0; (n + 1) as usize];
        ways(n, &mut memo)
    }
}

Rust · runnable

function climbStairs(n: number): number {
  const memo = new Array<number>(n + 1).fill(0);
  const ways = (k: number): number => {
    if (k <= 2) return k;
    if (memo[k] = 0) return memo[k];
    memo[k]= ways(k - 1) + ways(k - 2);
    return memo[k];
  };
  return ways(n);
}

TypeScript · runnable

Bottom-Up DP Array

TimeO(n)

SpaceO(n)

Fill a table from the base cases upward. Explicit, easy to reason about, easy to debug. Same asymptotic as memoization but without recursion overhead.

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        let n = n as usize;
        if n <= 2 {
            return n as i32;
        }
        let mut dp = vec![0; n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for i in 3..=n {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        dp[n]
    }
}

Rust · runnable

function climbStairs(n: number): number {
  if (n <= 2) return n;
  const dp = new Array<number>(n + 1).fill(0);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i]= dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

TypeScript · runnable

Two-Variable Rolling

TimeO(n)

SpaceO(1)

Recommended

The DP table only needs its two previous values. Collapse it to two scalars — same speed, constant extra space, best cache behavior. This is the form to ship.

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        let n = n as usize;
        if n <= 2 {
            return n as i32;
        }
        let (mut prev2, mut prev1) = (1u32, 2u32);
        for _ in 3..=n {
            let curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        prev1 as i32
    }
}

Rust · runnable

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev2 = 1;
  let prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

TypeScript · runnable

Trace

Two-variable rolling for n = 5:

step	prev2	prev1	curr = prev1 + prev2
init	1	2	—
3	2	3	3
4	3	5	5
5	5	8	8

Return prev1 = 8. ✓

Edge cases

n = 0 — not in LC's constraints; 1 (empty path) is the defensible interpretation. Clarify in interview.
n = 1 or n = 2 — handled by the early return.
Large n — O(log n) matrix exponentiation exists but isn't required by LC constraints. Mention it if asked.

ℹ️

Note

When you see "in how many ways…" with a small constant set of moves, the recurrence is almost always f(n) = f(n - a) + f(n - b) + …. Once you recognize the shape, the implementation is mechanical.

Takeaway

Every DP problem starts by asking "what does the answer at state n depend on?" For Climbing Stairs it's the two previous states. For House Robber (#198) it's two previous states with a different recurrence. For LIS (#300) it's all previous states filtered by a condition.

The recurrence is the DP. Everything else — memo vs table, 2D vs space-optimized — is implementation detail. The three approaches above are the same algorithm at different levels of polish.

Medium#198

House Robber

dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The ‘take or skip’ template.

Medium#300

Longest Increasing Subsequence

O(n²) DP first, then learn the O(n log n) patience sorting approach.

Medium#91

Decode Ways

Like climbing stairs but with constraints on which steps are valid.