Blind 75Easy

Climbing Stairs — Fibonacci DP

Reuse the recurrence f(n) = f(n-1) + f(n-2) with constant space to count distinct stair-climbing ways.

Dynamic Programming

View problem on LeetCode

Problem Statement

You can climb 1 or 2 steps at a time. How many distinct ways are there to climb n steps?

Why This Problem Matters

Introductory DP example that maps directly onto Fibonacci numbers.
Builds intuition for defining base cases and iterative recurrence.
Serves as a stepping stone for more complex step-counting problems.

Thought Process

Define recurrence

Ways to reach step n equals ways to reach n-1 plus ways to reach n-2.

Handle base cases explicitly

n <= 2 yields n ways; ensures recurrence seeds correctly.

Space optimise

Only previous two values are needed; store in two integers.

Step-by-Step Reasoning

Return n if n <= 2.
Initialise prev2 = 1, prev1 = 2 for steps 1 and 2.
Iterate i from 3 to n, compute current = prev1 + prev2, then shift variables.
Return prev1 after loop completes.

Dry Run

n = 4

Sequence builds 1,2,3,5 so answer is 5.

n = 1

Base case returns 1 immediately.

Complexity Analysis

Time

O(n)

Space

O(1)

Why

Linear iteration with constant storage.

Annotated Solution

JAVA

public class ClimbingStairs {
  public int climbStairs(int n) {
    if (n <= 2) {
      return n;
    }

    int prev2 = 1;
    int prev1 = 2;
    for (int i = 3; i <= n; i += 1) {
      int current = prev1 + prev2;
      prev2 = prev1;
      prev1 = current;
    }
    return prev1;
  }
}

Iterative Fibonacci recurrence provides a clean O(1) space solution.

Common Pitfalls

Forgetting to handle n = 0 or n = 1 leads to incorrect counts.
Using an array wastes space and may cause off-by-one indexing.
Integer overflow occurs for large n; mention mod arithmetic if constraints require.

Follow-Up Questions

What if you could take 1, 2, or 3 steps? Adapt the recurrence accordingly.
How would you compute the count modulo 1e9+7 for very large n?

Key Takeaways

Many DP problems reduce to Fibonacci-style recurrences.

Optimising space demonstrates deeper understanding beyond brute force.

Always check base cases carefully before iterating.