Climbing Stairs in Java: Solution, Explanation & Practice

Count distinct ways to climb n stairs (1 or 2 steps)

Problem summary

You can climb 1 or 2 stairs at a time. Given n stairs, count how many distinct ways you can reach the top. Classic DP problem!

Starter code

public class Main {
    public static void main(String[] args) {
        int n = 5;
        
        // ways(n) = ways(n-1) + ways(n-2)
        // From step n-1: take 1 step
        // From step n-2: take 2 steps
        // Print: Ways: 8
    }
}

Expected output and test cases

5 stairs → 8 ways
```
Ways: 8
```
3 stairs → 3 ways
```
Ways: 3
```
10 stairs → 89 ways
```
Ways: 89
```

Hints

This is Fibonacci in disguise!
To reach step n, you came from n-1 (1 step) or n-2 (2 steps)
So ways[n] = ways[n-1] + ways[n-2]
Base cases: ways[1]=1, ways[2]=2

Validated solution

Reveal Java solution

public class Main {
    static int ways(int stairs) {
        if (stairs <= 1) return 1;
        int previous = 1, current = 1;
        for (int step = 2; step <= stairs; step++) {
            int next = previous + current;
            previous = current; current = next;
        }
        return current;
    }
    public static void main(String[] args) { System.out.println("Ways: " + ways(5)); }
}

How to approach the problem

Every path to step n ends with either one step from n - 1 or two steps from n - 2. That recurrence is Fibonacci-shaped, and only the previous two counts are needed at once.

Approach

Define the zero and one stair base cases.
Add the previous two counts for each next step.
Slide the two stored values forward.

Time and space complexity

Time: O(n). Space: O(1).

Edge cases to test

There is one way to climb zero stairs: take no steps.
int overflows for sufficiently large stair counts.

Common mistakes

Using recursion without memoization and recalculating subproblems.
Returning zero for one stair.

Follow-up challenge

Allow step sizes 1, 2, and 3 and derive the new recurrence.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler