Introduction & Problem Explanation

The Climbing Stairs problem asks us to find the number of distinct ways to climb a staircase of n steps, where we can climb either 1 or 2 steps at a time.

This is a fundamental dynamic programming problem. To reach the n-th step, we must make our final move from either:

  1. The (n-1)-th step (by taking 1 step)
  2. The (n-2)-th step (by taking 2 steps)
Therefore, the total number of distinct ways to reach step n is simply the sum of the ways to reach step n-1 and the ways to reach step n-2. This recurrence relation: Ways(n) = Ways(n-1) + Ways(n-2) is identical to the mathematical definition of the Fibonacci sequence.

Illustration of Climbing Stairs subproblem transition tree in Java
Real-World Analogy: The Hops on a Path

Imagine a small frog hopping up a staircase. If the frog wants to get to the 4th step, it could have hopped there from the 3rd step (by doing a single hop) or from the 2nd step (by doing a double hop). The frog cannot reach the 4th step directly from the 1st step or ground level in a single move. Thus, all the paths the frog could take to reach the 4th step are just combinations of all paths to the 2nd step and all paths to the 3rd step.

The Algorithmic Approach

1. Dynamic Programming (O(n) Time, O(n) Space)

We can declare a memoization array dp where dp[i] stores the number of ways to reach the i-th step. We populate it iteratively from step 3 to n using dp[i] = dp[i-1] + dp[i-2]. This avoids repeating calculation of subproblems.

2. Space-Optimized Dynamic Programming (O(n) Time, O(1) Space)

Notice that to calculate the ways to reach the current step, we only ever need the values of the last two steps. Instead of keeping the entire dp array of size n + 1, we can keep track of only two variables: first (representing dp[i-2]) and second (representing dp[i-1]). We iteratively update them as we step forward. This reduces the space complexity from linear O(n) to a constant O(1).

Step-by-Step Execution Walkthrough

Let's trace the space-optimized algorithm for n = 5:

  1. Step 1 (Base Cases): For n = 5, since it's greater than 2, we initialize:
    • first = 1 (representing ways to reach step 1)
    • second = 2 (representing ways to reach step 2)
  2. Step 2 (Iteration i = 3):
    • Compute: third = first + second = 1 + 2 = 3.
    • Update state: first = 2, second = 3.
  3. Step 3 (Iteration i = 4):
    • Compute: third = first + second = 2 + 3 = 5.
    • Update state: first = 3, second = 5.
  4. Step 4 (Iteration i = 5):
    • Compute: third = first + second = 3 + 5 = 8.
    • Update state: first = 5, second = 8.
  5. Step 5 (Final Result): The loop ends. We return second, which is 8. There are 8 distinct ways to climb 5 stairs.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

  • if (n <= 2) return n;: Immediately handles the base cases where the number of stairs is 1 or 2, avoiding loop overhead.
  • int third = first + second;: Represents the core Fibonacci relation, combining the subproblem results of the two previous steps.
  • first = second; second = third;: Shifts our sliding window variables forward by one step, preparing them for the next iteration.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

public class ClimbingStairs {

    // Space-Optimized Dynamic Programming: Time O(N), Space O(1)
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int first = 1;  // Ways to reach step 1
        int second = 2; // Ways to reach step 2
        
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        
        return second;
    }

    public static void main(String[] args) {
        ClimbingStairs solver = new ClimbingStairs();
        int n = 5;

        System.out.println("--- Climbing Stairs Demonstration ---");
        System.out.println("Number of stairs (n): " + n);
        int ways = solver.climbStairs(n);
        System.out.println("Total distinct ways to climb: " + ways); // Expected: 8
    }
}

Conclusion

The Climbing Stairs problem is an excellent entry point into Dynamic Programming. We progress from a naive recursive solution with exponential complexity to an optimized iterative solution that runs in linear O(n) time and uses constant O(1) extra space.