Climbing Stairs easy

Description

You’re climbing a staircase. It takes n steps to reach the top. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

Examples

> Case 1:
    n = 2
    Output: 2
    Explanation: 1+1, or 2.
 
> Case 2:
    n = 5
    Output: 8
    Explanation: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1,
                 2+1+1+1, 1+2+2, 2+1+2, 2+2+1

Constraints

• 1 <= n <= 45

State design

1. What am I computing? Number of distinct ways to reach step i.
2. Dimensions? One — just i.
3. Base cases? dp[0] = 1 (one way to be at the start — don’t move), dp[1] = 1.
4. Transition? dp[i] = dp[i - 1] + dp[i - 2]. To reach step i, the last move was a 1-step (from i - 1) or a 2-step (from i - 2).
5. Order? Increasing i.

The recurrence is Fibonacci with shifted base cases. Same shape, same O(n) solution.

Try it yourself

def climb_stairs(n):
  # dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1
  pass

Code

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;
}

def climb_stairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

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;
}

Analysis

• Time: O(n) — one pass.
• Space: O(1) — two rolling variables.