Crack the Backend

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 step or 2 steps. Return the number of distinct ways you can climb to the top.

n is a positive integer (e.g. 1 <= n <= 45).
"Distinct ways" means different sequences of 1-step and 2-step moves (e.g. 1+2 and 2+1 are two different ways for n=3).
Base cases: n=0 can be defined as 1 way (already at top); n=1 has only one way (one step).

Key Observations

To reach step i, your last move was either a single step from i-1 or a double step from i-2. So the number of ways to reach i is the sum of the ways to reach i-1 and the ways to reach i-2.
This is exactly the Fibonacci recurrence: ways(i) = ways(i-1) + ways(i-2).
Base cases: ways(0) = 1, ways(1) = 1 (one way to stay at 0, one way to reach 1). We can then compute ways(2), ways(3), ... up to n.
Space can be reduced to O(1) by keeping only the last two values.

Approach

High-level: Define dp[i] = number of distinct ways to reach step i. Then dp[i] = dp[i-1] + dp[i-2] with dp[0] = 1, dp[1] = 1. Return dp[n].

Steps:

If n <= 1, return 1. Otherwise initialize prev2 = 1, prev1 = 1.
For i from 2 to n: cur = prev1 + prev2; then prev2 = prev1, prev1 = cur.
Return prev1 (which is dp[n]).

Implementation

Java

public int climbStairs(int n) {

    if (n <= 1) {
        return 1;
    }

    int prev2 = 1, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

Test Cases

n=2

Input

n = 2

Expected

2

Explanation

1+1 or 2.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

If you can climb 1, 2, or 3 steps, how does the recurrence change?