DSA AnimatorDSA animations
Climbing Stairs LC #70 Easy DP · Fibonacci
Problem

You climb a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways to reach the top?

Example 1
Input: n=2 → Output: 2 (1+1 or 2)
Example 2
Input: n=3 → Output: 3 (1+1+1, 1+2, 2+1)
Constraints: 1 ≤ n ≤ 45
Try Examples
Custom n:
Approach
Fibonacci DP — dp[i] = ways to reach step i
From step i you came from i−1 (1 step) or i−2 (2 steps). So dp[i] = dp[i-1] + dp[i-2]. Base: dp[1]=1, dp[2]=2.
Staircase & DP Array
Load an example.
Variables
i
—
dp[i-1]
—
dp[i-2]
—
ways
—
Step Logic
Press ▶ Play or Next Step to begin.
🏃
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[i] = ways to reach step i
2
From i: came from i−1 or i−2 → dp[i] = dp[i-1] + dp[i-2]
3
Base: dp[1]=1, dp[2]=2
4
Return dp[n]
Time
O(n)
Space
O(n)
Why This Works

To reach step i you must have come from step i−1 (took 1 step) or step i−2 (took 2 steps). So total ways = ways(i−1) + ways(i−2). Same as Fibonacci. dp[1]=1 (one way: {1}), dp[2]=2 ({1,1} or {2}).

How to solve Climbing Stairs

LeetCode 70 · Easy · Dynamic Programming · Pattern: 1D DP

Why the obvious approach is slow

Listing every sequence of 1 and 2 steps grows exponentially. But the count for each step can be built from smaller counts.

The key idea

Think about the very last move to step i. Either you came from step i −1 with a single step, or from step i minus 2 with a double step. So ways of i equals ways of i −1 plus ways of i minus 2. The base cases are 1 way to reach step 1, and 2 ways to reach step 2. It is the Fibonacci pattern in disguise.

Remember

Ask where the last move came from. The recurrence is the sum of the ways into the previous states.

Run the animation above on your own input, or watch the 1:31 video explanation of Climbing Stairs with a dry run and Java code.

More Dynamic Programming problems