Climbing Stairs Solution Explained – Step-by-Step

Dynamic Programming / Climbing Stairs

Climbing Stairs

Easy

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?

This is a classic dynamic programming problem that follows the Fibonacci sequence pattern.

Examples

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 to climb to the top:

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

Explanation

The key insight is that to reach step n, you must have come from either step n-1 (by taking 1 step) or step n-2 (by taking 2 steps). Therefore, the total number of ways to reach step n is the sum of ways to reach steps n-1 and n-2.

This recurrence relation f(n) = f(n-1) + f(n-2) is exactly the Fibonacci sequence! We can solve this using dynamic programming by building up from the base cases.

The base cases are:

There is 1 way to climb 0 stairs (stay where you are)
There is 1 way to climb 1 stair (take one step)

Idea Map

Start

Base cases: prev = 1, curr = 1

For i from 2 to n

1. next = prev + curr
2. prev = curr
3. curr = next

Return curr

Complexity Analysis

Time Complexity

O(n) - We iterate through the steps once, performing constant work at each step.

Space Complexity

O(1) - We only use three variables (prev, curr, next) regardless of input size.

Code


def climbStairs(n):
Initializes the function `climbStairs` which takes the number of steps `n` as input.
    if n <= 1:
Handle edge case: if n is 0 or 1, there's only 1 way to climb.
        return 1
Return 1 for base cases (0 or 1 steps).
    prev, curr = 1, 1
Initialize two variables: prev represents f(i-2), curr represents f(i-1), both start at 1.
    for i in range(2, n + 1):
Loop from step 2 up to and including step n, computing Fibonacci numbers iteratively.
        prev, curr = curr, prev + curr


Python's parallel assignment: prev gets old curr, curr gets prev + curr (next Fibonacci number).
    return curr
After the loop, curr holds f(n), the number of distinct ways to climb n stairs.


public int climbStairs(int n) {
Initializes the function `climbStairs` which takes the number of steps `n` as input and returns an integer.
    if (n <= 1) return 1;
Handle edge case: if n is 0 or 1, return 1 immediately (only one way to climb).
    int prev = 1, curr = 1;
Initialize two variables: prev represents f(i-2), curr represents f(i-1), both start at 1.
    for (int i = 2; i <= n; i++) {
Loop from step 2 up to and including step n, computing Fibonacci numbers iteratively.
        int next = prev + curr;
Calculate the next Fibonacci number by adding prev and curr.
        prev = curr;
Update prev to hold the old value of curr.
        curr = next;
Update curr to hold the newly computed next value.
    }
End of the for loop.
    return curr;
After the loop, curr holds f(n), the number of distinct ways to climb n stairs.
}
End of the function.


int climbStairs(int n) {
Initializes the function `climbStairs` which takes the number of steps `n` as input and returns an integer.
    if (n <= 1) return 1;
Handle edge case: if n is 0 or 1, return 1 immediately (only one way to climb).
    int prev = 1, curr = 1;
Initialize two variables: prev represents f(i-2), curr represents f(i-1), both start at 1.
    for (int i = 2; i <= n; i++) {
Loop from step 2 up to and including step n, computing Fibonacci numbers iteratively.
        int next = prev + curr;
Calculate the next Fibonacci number by adding prev and curr.
        prev = curr;
Update prev to hold the old value of curr.
        curr = next;
Update curr to hold the newly computed next value.
    }
End of the for loop.
    return curr;
After the loop, curr holds f(n), the number of distinct ways to climb n stairs.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Recursive solution without memoization

A naive recursive solution has exponential time complexity O(2^n). Always use the iterative DP approach or add memoization.

💡

Input n = 1

When n = 1, the answer is 1 (take one step). Don't forget to handle this edge case correctly.

✓

Using array instead of variables

You can use an array to store all Fibonacci numbers up to n, but using just two variables (prev, curr) is more space-efficient.

What is Dynamic Programming?

Dynamic programming is a powerful algorithmic technique that solves complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid redundant calculations, dramatically improving efficiency.

Learn more about dynamic programming →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Climbing Stairs' problem on LeetCode.

AlgoExplained.dev