BudiBadu Logo

Stair Lantern Routes

Dynamic Programming Easy 2 views
Like5

In the festival atrium, the lighting crew climbs a spiral staircase to hang fragile lanterns. Safety rules allow only one or two steps per move. In Stair Lantern Routes, your task is to calculate how many distinct move sequences reach the top exactly. The stage manager treats different orders (like 1+2 vs 2+1) as separate rehearsal plans, so every unique path must be counted!

The "secret sauce" here is Fibonacci-style DP. To reach step i, the crew must have come from either i-1 or i-2. By summing the ways to reach those two prior steps, you build the total for the current height efficiently. If the height is zero, there is one calm way to stay put while inspectors watch. Return the final count modulo 1,000,000,007 to keep the tally readable for the large festival team. This approach ensures the crew can split into pairs and start their drills on time without manual counting errors!

Examples

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 - Budibadu
Recommendation Algorithm Flow for Stair Lantern Routes - Budibadu

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;
    }
}