Count Distinct Ways to Reach the Nth Stairs

Consider a scenario where you have been given a number of stairs. You start at the 0th stair and need to reach the Nth stair. With each stride, you can choose to either ascend one step or two steps. Your task is to determine the number of distinct ways to move from the 0th to the Nth stair.

Input:

N = 3

Output:

3

Example:

The example scenarios could be:
- Climbing one step at a time: (0, 1), (1, 2), (2, 3)
- Climbing first two steps then one step: (0, 2), (2, 3)
- Climbing one step then two steps: (0, 1), (1, 3)

Constraints:

1

Question

Count Distinct Ways to Reach the Nth Stairs

Consider a scenario where you have been given a number of stairs. You start at the 0th stair and need to reach the Nth stair. With each stride, you can choose to either ascend one step or two steps. Your task is to determine the number of distinct ways to move from the 0th to the Nth stair.

Input:

N = 3

Output:

Example:

The example scenarios could be:
- Climbing one step at a time: (0, 1), (1, 2), (2, 3)
- Climbing first two steps then one step: (0, 2), (2, 3)
- Climbing one step then two steps: (0, 1), (1, 3)

Constraints:

1 <= T <= 100
0 <= N <= 10¹⁸

Note:

You do not need to print anything; input and output handling are already managed. Simply implement the required logic in the function.

Accepted Answer

The task is to find the number of distinct ways to move from the 0th to the Nth stair by ascending one or two steps at a time.

Use dynamic programming to solve this problem efficiently.
The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the number of ways to reach the (N-2)th stair.
Handle base cases for N=0 and N=1 separately.
Consider using memoization to avoid redundant calculations.
Example: For N=3, the number of distinct ways is 3: (0, 1, 2, 3), (0, 1, 3), (0, 2, 3).

Accepted Answer

public class Staircase {

// Function to count the number of ways to reach the nth stair
    public static int countWays(int n) {
        if (n &lt;= 1) {
            return 1;
        }
        
        // Array to store the number of ways to reach each stair
        int[] dp = new int[n + 1];
        
        // Base cases
        dp[0] = 1; // 1 way to stay on the 0th step
        dp[1] = 1; // 1 way to reach the 1st step (1 step)
        
        // Fill the dp array using the relation:
        // dp[i] = dp[i-1] + dp[i-2]
        for (int i = 2; i &lt;= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        // The result is the number of ways to reach the nth step
        return dp[n];
    }

public static void main(String[] args) {
        int n = 5; // Example input: Number of stairs
        System.out.println("Number of ways to reach the " + n + "th stair: " + countWays(n));
    }
}