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. Let's define dp[i] as the number of distinct ways to climb to 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 (where i > 1), you can either:

   • Take one step from step i-1: dp[i-1] ways
   • Take two steps from step i-2: dp[i-2] ways Therefore, the total number of ways to reach step i is dp[i] = dp[i-1] + dp[i-2].

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

4. Result: dp[n] will contain the total number of distinct ways to climb to the top (n steps).

Explanation

The dynamic programming approach avoids redundant calculations by storing the results of subproblems (number of ways to reach each step). The recursive relation captures the overlapping subproblems inherent in the problem: reaching step 3 depends on reaching step 2 and step 1, and so on. By building up the solution iteratively, we efficiently find the answer without repeatedly solving the same subproblems.

Code (Java)

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

        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 an array dp of size n+1 to store intermediate results. This can be optimized to O(1) by only storing the last two values of dp. (See optimized code below)

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

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int prev1 = 1, prev2 = 1;
        int current;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

This optimized version achieves the same time complexity but reduces space complexity to O(1) by only using three variables to store the necessary intermediate values.