⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#70) before relying on it.
Home → Algorithms → Climbing Stairs

Climbing Stairs

An interactive visualization of the classic dynamic programming problem. Watch how the Fibonacci-like recurrence builds up to count the number of distinct ways to climb n stairs, taking either 1 or 2 steps at a time.

Dynamic Programming LeetCode 70 ↗ Easy

The Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example: If n = 3, there are 3 ways: (1+1+1), (1+2), or (2+1).
Constraints: 1 ≤ n ≤ 45

Interactive Visualization

Speed:
Staircase Visualization
DP Array
Code
fun climbStairs(n: Int): Int {    if (n <= 1)        return 1    val dp = IntArray(n + 1)    dp[0] = 1  // base case    dp[1] = 1  // base case    for (i in 2..n)        dp[i] = dp[i - 1] + dp[i - 2]    return dp[n]}
Status
Press Step or Play to begin.

How It Works

Key Insight

To reach stair i, you could have come from stair i-1 (taking 1 step) or from stair i-2 (taking 2 steps). Therefore, the number of ways to reach stair i is the sum of the ways to reach i-1 and i-2: dp[i] = dp[i-1] + dp[i-2]. This creates a Fibonacci-like sequence!

The Algorithm

  • Base cases: dp[0] = 1 (one way to stay at ground), dp[1] = 1 (one way to climb 1 stair)
  • Each iteration: For stair i from 2 to n, compute dp[i] = dp[i-1] + dp[i-2]
  • Recurrence relation: Each dp value depends only on the previous two values
  • Final answer: dp[n] contains the total number of distinct ways to climb n stairs
  • Pattern: The sequence follows Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, ...

Complexity

Time O(n)
Space O(1)

We iterate through n stairs once, and while this implementation uses an array, the space can be optimized to O(1) by keeping only the last two values (since we only need dp[i-1] and dp[i-2]).