Climbing Stairs

easy Dynamic Programming

You are climbing a staircase that has n steps to reach the top. Each time you can climb either 1 or 2 steps. Return the number of distinct ways you can climb to the top. The input n is a positive integer where 1 <= n <= 45.

Example

n = 5

Output: 8

There are 8 distinct ways to climb 5 stairs using 1- or 2-steps: [1,1,1,1,1], [2,1,1,1], [1,2,1,1], [1,1,2,1], [1,1,1,2], [2,2,1], [2,1,2], [1,2,2].

dp[i] = dp[i-1] + dp[i-2]. At each step you can arrive from 1 or 2 steps below. This is the same recurrence as Fibonacci — the number of ways to reach step i is the sum of ways to reach the two steps before it.

Why this works

To reach step n, you must have come from either step n-1 (took 1 step) or step n-2 (took 2 steps). So the number of ways to reach step n is the sum of ways to reach those two previous steps. This is exactly the Fibonacci sequence, and you only need two variables instead of a full array.

Step by step

Handle base cases — there is 1 way to reach step 1 (one single step) and 2 ways to reach step 2 (1+1 or 2).
Build up from step 3 — for each step, add the ways from the two previous steps: curr = prev1 + prev2.
Slide the window — shift prev2 = prev1 and prev1 = curr to move forward without storing the full array.

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

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;  // base cases: 1 way to reach step 1, 2 ways to reach step 2
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;  // ways to get here = ways from one step below + two steps below
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev2 = 1, prev1 = 2;  // base cases: 1 way to reach step 1, 2 ways to reach step 2
        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;  // ways to get here = ways from one step below + two steps below
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2  # base cases: 1 way to reach step 1, 2 ways to reach step 2
    for i in range(3, n + 1):
        curr = prev1 + prev2  # ways to get here = ways from one step below + two steps below
        prev2 = prev1
        prev1 = curr
    return prev1