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?

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

Constraints:

• 1 <= n <= 45

Approach: Dynamic Programming (Bottom-Up)

Algorithm

1. Let dp[i] be the number of distinct ways to reach step i
2. Base cases: dp[0] = 1 (one way to stay at the ground), dp[1] = 1
3. To reach step i, you can come from step i - 1 (climb 1 step) or step i - 2 (climb 2 steps), so dp[i] = dp[i - 1] + dp[i - 2]
4. Return dp[n]

Time & Space Complexity

• Time Complexity: O(n) - single loop from 2 to n
• Space Complexity: O(n) - DP array of size n + 1 (can be reduced to O(1))

Java Implementation

public class ClimbingStairs {

    /**
     * Count the distinct ways to climb to the top of an n-step staircase.
     * @param n Number of steps
     * @return Number of distinct ways
     */
    public static 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];
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 2");
        System.out.println("Output: " + climbStairs(2)); // Expected: 2

        System.out.println("Input: n = 3");
        System.out.println("Output: " + climbStairs(3)); // Expected: 3
    }
}

Space-Optimized Implementation (O(1) Space)

Since dp[i] only depends on the previous two values, two variables are enough.

public class ClimbingStairsOptimized {

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

        int prev2 = 1; // dp[0]
        int prev1 = 1; // dp[1]

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

        return prev1;
    }
}

Example Walkthrough

For n = 3:

1. dp[0] = 1, dp[1] = 1
2. dp[2] = dp[1] + dp[0] = 1 + 1 = 2
3. dp[3] = dp[2] + dp[1] = 2 + 1 = 3

Ways: 1+1+1, 1+2, 2+1. Answer: 3.

Key Points

1. Fibonacci Pattern: The number of ways follows the Fibonacci sequence
2. Recurrence Relation: dp[i] = dp[i - 1] + dp[i - 2]
3. O(1) Space Option: Only the last two values are needed during the loop
4. Small Constraint: n <= 45, so the answer fits comfortably in an int
5. Intuition: The last move is either a single step or a double step