Course contentsShow
← Computer Science
Lesson 924 of 2,87222. Dynamic ProgrammingFree lesson

Climbing Stairs Problem

Count ways to reach the top of stairs taking 1 or 2 steps at a time using dynamic programming.

Climbing Stairs Problem

What you'll learn: How to count all the different ways you can climb a staircase by taking 1 or 2 steps at a time using dynamic programming.

The Problem

Imagine you're at the bottom of a staircase with n steps. Each move, you can either climb 1 step or 2 steps. How many distinct ways can you reach the top?

For example, with 3 steps, there are 3 ways:

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

Why It's Perfect for DP

This problem has overlapping subproblems and optimal substructure. To reach step n, you must have come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). So:

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

Sound familiar? It's the Fibonacci pattern! But we're counting paths, not generating numbers.

The Solution

Base cases:

  • ways(0) = 1 (one way to stay at ground: do nothing)
  • ways(1) = 1 (only one 1-step)

Bottom-up approach: Build a table from step 0 upward, filling each entry by adding the previous two values—just like the Fibonacci sequence with memoization or tabulation.

Analogy

Think of it like routing options on a map: the number of paths to destination n equals all paths to the previous two waypoints combined.

Key Takeaway: The Climbing Stairs problem is essentially Fibonacci in disguise—use dynamic programming to avoid recalculating overlapping subproblems, achieving O(n) time and O(1) space with optimization.