ToolMight LogoToolMight
EasyDynamic ProgrammingPattern: Fibonacci SequencePattern: Bottom-Up DPPattern: State Transition

Climbing Stairs

Count the distinct ways to reach the top of an n-step staircase when hopping 1 or 2 steps at a time. The premier gentle introduction to Dynamic Programming and state transition.

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?

Examples & Constraints

Example 1
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top: 1. 1 step + 1 step, 2. 2 steps.
Example 2
Input: n = 3
Output: 3
Explanation: There are three ways: 1. 1 + 1 + 1, 2. 1 + 2, 3. 2 + 1.
Constraints
  • 1 <= n <= 45

Space-Optimized DP (Fibonacci State Transition)

Optimal Approach
Time:O(n)
Space:O(1)

Recognize that ways to reach step n is ways(n - 1) + ways(n - 2). Maintain only two previous states for O(1) space.

Time ComplexityO(n)

A single loop from step 3 up to N.

Space ComplexityO(1)

Only two variables (prev1, prev2) are maintained in memory.

Underlying algorithmic logic

The Core Mental Model: Look At Your Last Hop

Instead of thinking forward from the bottom of the stairs, stand at the top step (`n`) and look backwards:

Because you can only jump 1 step or 2 steps, your final hop onto step n could have ONLY originated from two places:

  1. You were on step `n - 1` and hopped 1 step.
  2. You were on step `n - 2` and hopped 2 steps.

There is no other physical way to land on step n.
Therefore, the total distinct ways to reach step n is simply the sum of ways to reach both preceding steps:
ways(n) = ways(n - 1) + ways(n - 2)

Why This Is Fibonacci In Disguise

Base cases:

  • ways(1) = 1 (just [1])
  • ways(2) = 2 ([1+1], [2])
  • ways(3) = 1 + 2 = 3
  • ways(4) = 2 + 3 = 5

Avoiding The O(2ⁿ) Recursive Trap

If you code this as naive recursion return climb(n - 1) + climb(n - 2), the computer re-computes subproblems exponentially. At n = 45, that takes 2⁴⁵ ≈ 35 trillion calculations!

Step-by-Step Engineering Flow (Two Variables in O(1) Space)

  1. Handle Base Cases: If n <= 2, return n immediately (n = 1 has 1 way; n = 2 has 2 ways).
  2. Initialize Two Running States:
  • Set prev1 = 1 (ways to reach step 1).
  • Set prev2 = 2 (ways to reach step 2).
  1. Iterative Window Slide: For each step i from 3 up to n:
  • Calculate current step ways: curr = prev1 + prev2.
  • Shift the state window forward: prev1 = prev2, then prev2 = curr.
  1. Return Answer: When the loop finishes, prev2 holds the total distinct ways to reach step n.

This yields an optimal `O(n)` time and `O(1)` memory solution.

Step-by-step execution walkthrough

1
Base States

For n = 1 -> 1 way. For n = 2 -> 2 ways.

prev1 = 1, prev2 = 2
2
Step 3

curr = 1 + 2 = 3. Shift: prev1 = 2, prev2 = 3.

ways(3) = 3
3
Step 4

curr = 2 + 3 = 5. Shift: prev1 = 3, prev2 = 5.

ways(4) = 5
Advantages
  • •Optimal O(n) runtime
  • •Constant O(1) space
  • •Introductory paradigm for dynamic programming state transitions
Trade-offs
  • •None for N <= 45

Code Implementations

Copy & paste production-ready solutions for Space-Optimized DP (Fibonacci State Transition) in your language of choice

File: solution.py
Python
def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev1, prev2 = 1, 2
    for _ in range(3, n + 1):
        prev1, prev2 = prev2, prev1 + prev2
    return prev2
if __name__ == "__main__":
    print(f"climb_stairs(2): {climb_stairs(2)}")
    print(f"climb_stairs(3): {climb_stairs(3)}")
Interactive visualizer available

Understand Recursion & Fibonacci Visually

Observe compiler stack frames tracking self-referencing operations and tree calculations. Test live edge cases and watch memory state transitions step-by-step.

Launch Recursion & Fibonacci Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasySliding Window
Visualizer

Best Time to Buy and Sell Stock

Determine the maximum single-transaction profit from daily stock prices. A classic demonstration of how tracking a running minimum transforms an O(n²) pair search into an O(n) single pass.

1 approach(O(n))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic
MediumDynamic Programming
Visualizer

Maximum Subarray (Kadane's Algorithm)

Find the contiguous slice of an array that yields the largest sum. Kadane's algorithm demonstrates the art of shedding negative historical baggage in O(n) linear time.

1 approach(O(n))
Learn logic