Climbing Stairs — DSA

Problem

You're climbing a staircase with n steps. Each move, you can climb either 1 step or 2 steps. In how many distinct ways can you reach the top?

n = 2   →   2      (1+1, 2)
n = 3   →   3      (1+1+1, 1+2, 2+1)
n = 5   →   8

Order matters: 1+2 and 2+1 are different ways.
1 ≤ n ≤ 45 in the classic version. The answers grow like Fibonacci numbers, so larger n would overflow an int.
This is the gentlest introduction to dynamic programming: the number of ways to reach step n is built from the answers for steps n-1 and n-2.

Examples

Example 1

Input: n = 3

Output: 3

Explanation: Three ways: 1+1+1, 1+2, 2+1.

Constraints

•1 <= n <= 45

Hints

Hint 1

State the recurrence out loud before coding: to reach step n, your last move was either a 1-step from n-1, or a 2-step from n-2 — so ways(n) = ways(n-1) + ways(n-2).

Hint 2

This is structurally identical to the Fibonacci sequence — recognizing that connection is the whole insight.

Hint 3

You don't need an array to hold every intermediate value — only the last two values are ever needed at once.

Solutions

public int climbStairsBruteForce(int n) {
    if (n <= 2) return n;
    return climbStairsBruteForce(n - 1) + climbStairsBruteForce(n - 2);
}

Time: O(2^n) · Space: O(n) recursion depth