← Back to DSA Animator
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}).