The Problem Statement

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: n = 2

There are two ways to climb:

  • 1 step + 1 step
  • 2 steps

Example: n = 3

There are three ways to climb:

  • 1 step + 1 step + 1 step
  • 1 step + 2 steps
  • 2 steps + 1 step

Building the Intuition

Let's analyze the number of ways for small values of `n`. A clear pattern emerges. To reach step `n`, you must have come from either step `n-1` or step `n-2`. Therefore, the total ways to reach `n` is the sum of the ways to reach `n-1` and `n-2`.

This gives us the recurrence relation: Ways(n) = Ways(n-1) + Ways(n-2). This is the famous Fibonacci sequence!

Ways to Climb vs. n

Visualizing the Approaches

Understanding the brute-force recursive approach is key. It explores every single path, leading to many repeated calculations. This interactive tree shows all the function calls for a given `n`. Notice how many nodes are recalculated!

Recursive Tree Explorer

Redundant Call
Base Case

Comparing Performance

Dynamic Programming (DP) optimizes the recursive approach by storing results of subproblems (memoization) or by building the solution from the bottom up (tabulation). This dramatically improves performance. Hover over the bars to see the complexities.

Code Explorer

Dive into the actual implementations for each approach. Click the tabs to switch between the different solutions and see how the logic evolves from brute-force to the most optimal solution.

Tries all possibilities (1-step or 2-step) from the current step. This leads to an exponential number of calculations because subproblems are solved repeatedly.

class Solution { public int climbStairs(int n) { if (n < 0) return 0; if (n == 0) return 1; return climbStairs(n - 1) + climbStairs(n - 2); } }
Time: O(2ⁿ) | Space: O(n) (recursion stack)