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 to Solve

This problem can be solved using dynamic programming. We can define a DP array dp where dp[i] represents the number of distinct ways to reach the i-th step.

1. 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)

2. Recursive Relation: To reach step i, you can either come from step i-1 (by taking one step) or from step i-2 (by taking two steps). 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]

3. Iteration: Iterate through the DP array, calculating dp[i] using the recursive relation until you reach dp[n].

4. Return: The value of dp[n] represents the total number of distinct ways to climb to the top.

Explanation

The dynamic programming approach avoids redundant calculations by storing the results of subproblems (the number of ways to reach each step). The recursive relation ensures that we correctly account for all possible combinations of 1-step and 2-step jumps.

Code (C#)

using System;

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 1) return n; // Base cases

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

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

        return dp[n];
    }
}

Complexity Analysis

• Time Complexity: O(n) - We iterate through the DP array once.
• Space Complexity: O(n) - We use a DP array of size n+1. This could be optimized to O(1) by only storing the last two values. See optimized code below.

Optimized Code (C#) - O(1) Space Complexity

using System;

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 1) return n;

        int prev1 = 1; // dp[i-1]
        int prev2 = 1; // dp[i-2]
        int current = 0; // dp[i]

        for (int 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.