Code Logo

Stair Lantern Routes

Published at05 Jan 2026
Created by
Easy 4 views
Like5

You are climbing a staircase and can move either 1 step or 2 steps at a time. The question is how many different routes can reach exactly the top.

Order matters here. Taking 1 + 2 is a different route from taking 2 + 1, because they happen in a different sequence.

For example, if steps = 5, the answer is 8. If steps = 3, the routes are 1+1+1, 1+2, and 2+1, so the answer is 3. If steps = 0, the answer is 1 because doing nothing is one valid way to already be at the top.

So the task is to count every ordered sequence of 1-step and 2-step moves that lands exactly on the final stair.

Example Input & Output

Example 1
Input
steps = 5
Output
8
Explanation

Eight ordered combinations of single and double steps reach the fifth stair.

Example 2
Input
steps = 0
Output
1
Explanation

Staying at the floor counts as one valid plan.

Example 3
Input
steps = 3
Output
3
Explanation

Three plans exist: 1+1+1, 1+2, and 2+1.

Algorithm Flow

Recommendation Algorithm Flow for Stair Lantern Routes
Recommendation Algorithm Flow for Stair Lantern Routes

Solution Approach

This is one of the simplest dynamic programming patterns. Let dp[n] be the number of ways to reach step n.

To arrive at step n, the last move must have come from either step n - 1 with a 1-step jump or from step n - 2 with a 2-step jump. So the recurrence is:

dp[n] = dp[n - 1] + dp[n - 2]

The base values are:

dp[0] = 1

dp[1] = 1

From there, you fill upward until the requested number of steps. This is why the problem follows the Fibonacci pattern.

You can store the whole DP array, or just keep the previous two values to get O(1) extra space.

Best Answers

java
class Solution {
    public int calculate_climb_ways(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = a + b;
            a = b; b = tmp;
        }
        return b;
    }
}