Climbing Stairs easy

Problem Statement

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?

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps

Example 2:

Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top.

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

Steps and Explanation

This problem can be solved using dynamic programming. Let dp[i] represent the number of distinct ways to climb to the i-th step.

  • Base Cases:

    • dp[0] = 1 (There's one way to reach step 0: do nothing)
    • dp[1] = 1 (There's one way to reach step 1: take one step)

  • Recursive Relation: To reach step i, you can either come from step i-1 (by taking a single step) or from step i-2 (by taking a double step). Therefore, the number of ways to reach step i is the sum of the ways to reach step i-1 and step i-2: dp[i] = dp[i-1] + dp[i-2]

  • Iteration: We iterate from i = 2 up to n, calculating dp[i] using the recursive relation.

Code (Typescript)

function climbStairs(n: number): number {
    if (n <= 1) return 1; // Base cases

    const dp: number[] = new Array(n + 1);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

Complexity Analysis

  • Time Complexity: O(n). The loop iterates n times.
  • Space Complexity: O(n). We use a dp array of size n+1 to store intermediate results. This could be optimized to O(1) by only storing the last two values. See optimized code below.

Optimized Code (Typescript) - O(1) Space Complexity

function climbStairsOptimized(n: number): number {
    if (n <= 1) return 1;

    let prev1 = 1;
    let prev2 = 1;
    let current = 0;

    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

This optimized version achieves the same result while only using constant extra space. It iteratively updates prev1 and prev2 to represent the last two calculated values, avoiding the need for an array.