Climbing Stairs

Given : A staircase with n steps.
Objective : Finding out the number of ways to reach the top of the staircase if you are allowed to take 1 step or 2 steps at a time.

Example : If there are 4 steps in the staircase, then below are the possible ways to reach the top.

Way (s)	Steps taken
1	1 1 1 1
2	2 1 1
3	1 2 1
4	1 1 2
5	2 2

Recursive approach
Consider a staircase with 3 steps. As only 1 or 2 steps could be taken,

To go to stair 1, there is only one way i.e using 1 step from the ground.
[ 1 ]
To go to stair 2, one way could be using 2 steps from the ground or using 1 step from stair 1.
[ 1 - 1 ]
[ 2 ]
To go to the topmost stair 3, we could take a step (s) from stair 1 or stair 2.
Note : We are not trying to reach stair 2 from stair 1 as that path has already been considered.
From stair 1, we could only take 2 steps i.e [ stair 1 -> 2 ] to reach the topmost stair
Thus we get a path,
[ 1 ] -> [ 2 ]
From stair 2, we could take 1 step i.e [ stair 2 -> 1 ]
As stair 2 could be reached in 2 ways [ 1 - 1 ] and [ 2 ], we get the below paths,
[ 1 - 1 ] -> [ 2 ]
[ 2 ] -> [ 1 ]

Climbing_Stairs

Thus, the recursive algorithm could be as below..

int Count_Ways ( Steps n )

If n equals 0, 1 or 2, then
return n
Else
return Count_Ways ( n - 1 ) + Count_Ways ( n - 2 )

Note : The recursive algorithm times out if the number of steps (n) is greater than 40. As the recursive solution tries to solve the overlapping subproblems, it proves to be highly inefficient. A dynamic programming approach as shown in the below code is the better of the two.

Program for counting the distinct number of ways to reach the top of a staircase.
Ref : Leetcode Climbing stairs problem

def CountWays_DP(n) :
    ways = [ 0, 1, 2 ] 
    for i in range(3, n + 1) :
        ways.append(ways[i-1] + ways[i-2])
    return ways[n]

def CountWays_Rec (n) :
    if (n == 0 or n == 1 or n == 2) :
        return n
    return ( CountWays_Rec(n-1) + CountWays_Rec(n-2) )

def main() :

    steps = int(input("Enter steps : "))
    print("[DP] Ways of reaching the top : " + str(CountWays_DP(steps)))
    print("[Recursion] Ways of reaching the top : " + str(CountWays_Rec(steps)))

if __name__ == "__main__" :
    main()

Output

Enter steps : 4
[DP] Ways of reaching the top : 5
[Recursion] Ways of reaching the top : 5

Enter steps : 8
[DP] Ways of reaching the top : 34
[Recursion] Ways of reaching the top : 34

Enter steps : 9
[DP] Ways of reaching the top : 55
[Recursion] Ways of reaching the top : 55

#include<iostream>
using namespace std;

class ClimbStairs {

    public:
    long long CountWays_DP(int n) {
        long long ways[101] = {0};
        ways[0] = 0;
        ways[1] = 1;
        ways[2] = 2;
        for (int i=3; i<=n; i++) {
            ways[i] = ways[i-1] + ways[i-2];
        }   
        return ways[n];
    }   

    long long CountWays_Rec (int n) {
        if (n == 0 || n == 1 || n == 2)
            return n;
        return ( CountWays_Rec(n-1) + CountWays_Rec(n-2) );
    }   
};

int main() {

    ClimbStairs cs;
    int steps;

    cout << "Enter steps : ";
    cin >> steps;
    cout << "[DP] Ways of reaching the top : " << cs.CountWays_DP(steps) << endl;
    cout << "[Recursion] Ways of reaching the top : " << cs.CountWays_Rec(steps) << endl;
 
    return 0;
}

Output

Enter steps : 30
[DP] Ways of reaching the top : 1346269
[Recursion] Ways of reaching the top : 1346269

Enter steps : 10
[DP] Ways of reaching the top : 89
[Recursion] Ways of reaching the top : 89

Enter steps : 5
[DP] Ways of reaching the top : 8
[Recursion] Ways of reaching the top : 8

import java.util.Scanner;

class ClimbStairs {

    long CountWays_DP (int n) {
        long[] ways = new long[101];
        ways[0] = 0;
        ways[1] = 1;
        ways[2] = 2;

        for (int i=3; i<=n; i++) {
            ways[i] = ways[i-1] + ways[i-2];
        }   
        return ways[n];
    }

    long CountWays_Rec (int n) {
        if (n == 0 || n == 1 || n == 2)
            return n;
        return ( CountWays_Rec(n-1) + CountWays_Rec(n-2) );
    }

    public static void main (String[] args) {
    
        ClimbStairs cs = new ClimbStairs();
        int steps;
    
        System.out.print("Enter steps : ");
        Scanner sc = new Scanner(System.in);
        steps = sc.nextInt();
        System.out.println("[DP] Ways of reaching the top : " + cs.CountWays_DP(steps));
        System.out.println("[Recursion] Ways of reaching the top : " + cs.CountWays_Rec(steps));
    }   
}

Output

Enter steps : 7
[DP] Ways of reaching the top : 21
[Recursion] Ways of reaching the top : 21

Enter steps : 4
[DP] Ways of reaching the top : 5
[Recursion] Ways of reaching the top : 5

Enter steps : 40
[DP] Ways of reaching the top : 165580141
[Recursion] Ways of reaching the top : 165580141

Enter steps : 6
[DP] Ways of reaching the top : 13
[Recursion] Ways of reaching the top : 13