LeetEye LeetEye
Easy 1D Dynamic Programming ~5 min

Climbing Stairs

1d-dp climbing-stairs

Problem

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

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)
Key Insight

To reach step n, you either came from step n-1 (took 1 step) or step n-2 (took 2 steps).

To reach step n, add ways to reach n-1 and n-2. It's Fibonacci.

How to Approach This Problem

Pattern Recognition: When you see keywords like climbing stairs 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 To reach step n, the last move was:
Answer: Either 1 or 2 steps
From any step, you can take 1 or 2 steps. So you arrived from n-1 or n-2.
2 ways(n) equals:
Answer: ways(n-1) + ways(n-2)
Ways from n-1 (then take 1 step) PLUS ways from n-2 (then take 2 steps).
3 Base cases are:
Answer: ways(0) = 1, ways(1) = 1
ways(1)=1 (one way: take 1 step). ways(0)=1 (one way: do nothing - you're there).
4 The sequence 1, 1, 2, 3, 5, 8, 13... is:
Answer: Fibonacci sequence
Each term is sum of previous two. Classic Fibonacci.
5 Instead of array, we only need:
Answer: Two variables
Only need previous two values to compute current.

Solution

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    
    # Only need previous two values
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    
    return prev1

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye