14. Climbing Stairs

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

Input: n = 2
Output: 2
Explanation: There are two ways: 1+1 steps or 2 steps.

Input: n = 3
Output: 3
Explanation: Three ways: 1+1+1, 1+2, or 2+1.

Problem Breakdown:

1. This is a Fibonacci-like problem. To reach step n, you can come from step n-1 (1 step) or step n-2 (2 steps). So ways(n) = ways(n-1) + ways(n-2).

• # ways(n) = ways(n-1) + ways(n-2)
  # Base cases: ways(1) = 1, ways(2) = 2

2. Use two variables to track the previous two values. Initialize both to 1 (representing the base cases for steps 0 and 1).

• one = 1
  two = 1

3. Iterate n-1 times, computing each new value as the sum of the two previous values. This is bottom-up dynamic programming.

• for i in range(n - 1):
      temp = one
      one = one + two
      two = temp

4. After the loop, the variable 'one' contains the total number of distinct ways to climb n stairs.

• return one

Summary:

This follows the Fibonacci pattern. The number of ways to reach step n is the sum of ways to reach n-1 and n-2. Use bottom-up DP with two variables to achieve O(1) space instead of O(n) with an array.

Time and Space Complexity:

Time Complexity: O(n) - we iterate n-1 times.

Space Complexity: O(1) - only two variables used.

Python Solution:

def climbStairs(n):
    one = 1
    two = 1
    for i in range(n - 1):
        temp = one
        one = one + two
        two = temp
    return one

JavaScript Solution:

var climbStairs = function(n) {
    let one = 1, two = 1;
    for (let i = 0; i < n - 1; i++) {
        const temp = one;
        one = one + two;
        two = temp;
    }
    return one;
};

Java Solution:

class Solution {
    public int climbStairs(int n) {
        int one = 1, two = 1;
        for (int i = 0; i < n - 1; i++) {
            int temp = one;
            one = one + two;
            two = temp;
        }
        return one;
    }
}