Problem:

You are given n stairs. At each step, you can either climb 1 stair or 2 stairs. Find the total number of distinct ways to reach the top of the staircase.

Approach:

The problem can be solved by recognizing that the number of ways to reach step n is the sum of the number of ways to reach step n-1 and step n-2. This is because you can get to step n by:

• Taking a 1-step from n-1, or
• Taking a 2-step from n-2.

Hence, this problem is analogous to finding the nth Fibonacci number.

Solution Explanation:

1. Base Cases:

   • If n == 1, there is only one way to reach the top (just take one step).
   • If n == 2, there are two ways to reach the top (either take two 1-steps or one 2-step).

2. Iterative Solution: For n > 2, we use an iterative approach to compute the number of ways to reach step n. We can use two variables to keep track of the number of ways to reach the previous two steps (a and b), and compute the current value iteratively.

3. Time Complexity:
   The time complexity is O(n) because we are iterating over the stairs once.

4. Space Complexity:
   The space complexity is O(1) as we only need a constant amount of extra space for storing intermediate results.

C Code:

#include <stdio.h>

int climbStairs(int n)
{
    if (n <= 2) return n;  // Base cases
    int a = 1, b = 2, c = 0;
    for (int i = 3; i <= n; i++)
    {
        c = a + b;  // Calculate number of ways to reach the current step
        a = b;      // Update previous two steps
        b = c;
    }
    return b;  // Return the number of ways to reach the top (step n)
}

int main()
{
    int n = 5;  // Number of stairs
    printf("%dn", climbStairs(n));  // Output the total number of ways to reach the top
    return 0;
}

Explanation:

1. Base Case:
   If n is 1 or 2, we return n because there are n ways to reach the top.

2. Iterative Loop:
   Starting from step 3, we iteratively compute the number of ways to reach the current step (c), which is the sum of the previous two steps (a and b). We then update a and b for the next iteration.

3. Final Result:
   After the loop finishes, the variable b holds the number of ways to reach step n, which is printed in the main function.

Example:

For n = 5:

• Step 1: 1 way (1)
• Step 2: 2 ways (1+1 or 2)
• Step 3: 3 ways (1+1+1, 1+2, 2+1)
• Step 4: 5 ways (1+1+1+1, 1+2+1, 2+1+1, 2+2, 1+1+2)
• Step 5: 8 ways (sum of the previous two)

The output for n = 5 is 8.