Find Total Number Of Ways To Reach The N’th Stair In C#

In this article, we will see how to find total ways to reach the n’th stair from the bottom in C#.

Given a staircase, where we need to find the total number of ways to reach the n'th stair from the bottom of the staircase.

A person can only climb either the 1 or 2 stairs at a time. 

To understand it let's take an example,

The total number of ways to reach the 4th stair is 5,
 
1 step + 1 step + 1 step + 1 step
2 steps + 1 step + 1 steps
1 step + 2 steps
1 step + 2 steps + 1 steps
2 steps + 2 steps

Problem

Let's understand T(n) is the total number of ways to reach the n'th stair from the bottom form staircase. Since a person is only allowed to climb either 1 or 2 stairs at a time, so the person can reach the n'th stair from either the (n-1)'th stair, (n-2)'th stair.

Considering this is the recurrence relation T(n), can be written as:

T(n) = T(n-1) + T(n-2) , where n >= 0 and the
T(0) = 1, T(1) = 1

Problem-solving 

There are many ways to perform to count the number of ways to reach the nth stair in C#.

One common way to is the Bottom-up/ dynamic approach and another is the Top-up/Recursive approach.

Bottom-Up Approach/ dynamic approach

The bottom-up approach uses dynamic programming, where it starts by calculating the number of ways to reach the first few staircases (in this case, the first two stairs) and then uses these values to calculate the number of ways to reach higher stairs.

static void Main(string[] args) {
    Console.WriteLine("give number of stairs to reach");
    int number = Convert.ToInt16(Console.ReadLine());
    Console.WriteLine("Number of ways to reach:- " + Class1.CountStairWays(number));
}
public static int CountStairWays(int stairNumber) {
    if (stairNumber <= 0) {
        return 0;
    } else if (stairNumber == 1) {
        return 1;
    } else if (stairNumber == 2) {
        return 2;
    }
    int[] stairArray = new int[stairNumber + 1];
    stairArray[0] = 0;
    stairArray[1] = 1;
    stairArray[2] = 2;
    for (int i = 3; i <= stairNumber; i++) {
        stairArray[i] = stairArray[i - 1] + stairArray[i - 2];
    }
    return stairArray[stairNumber];
}

The time complexity of the above solution is O(n), where n is the size of the input, And The space complexity of the above solution is O(n).

Top-up approach/ recursive function and memorization

This function uses the top-down approach, where it starts by trying to find the number of ways to reach the nth stair by breaking the problem down into smaller sub-problems (in this case, finding the number of ways to reach the n-1th and n-2nd stairs) and then combining the solutions to these subproblems to find the solution to the original problem.

Note that the above examples use the Fibonacci sequence, where each number is the sum of the two preceding ones, starting from 0 and 1.

static void Main(string[] args) {
    Console.WriteLine("give number of stairs to reach");
    int number = Convert.ToInt16(Console.ReadLine());
    int[] stairArray = new int[number + 1];
    Console.WriteLine("Number of ways to reach:- " + Class1.CountStairWaysUsingRecursive(number, stairArray));
}
public static int CountStairWaysUsingRecursive(int stairNumber, int[] stairArray) {
    if (stairNumber <= 0) {
        return 0;
    } else if (stairNumber == 1) {
        return 1;
    } else if (stairNumber == 2) {
        return 2;
    }
    if (stairArray[stairNumber] == 0) {
        stairArray[stairNumber] = CountStairWaysUsingRecursive(stairNumber - 1, stairArray) + CountStairWaysUsingRecursive(stairNumber - 2, stairArray);
    }
    return stairArray[stairNumber];
}

Output