need an explanation for this answer? contact us directly to get an explanation for this answer

1) Recursive Approach:

In this approach, we will make recursive calls each time until our base case reaches. We have the following base case:

if(n==0):
    then 1, as there is only one way to step on with n steps.
if(n<0)
    then 0, as stair numbers cannot be negative.

Now each of the current stairs depends on the previous three stairs since we can take 1 2 or 3 step climb from the current step.

Therefore the overall recursion function f(n) becomes:

f(n)= 0,if(n<0)
    1, if(n==0)
    f(n-1)+f(n-2)+f(n-3), otherwise.

Time Complexity for the above approach in the worst case is exponential.

Space Complexity for the above approach is the liner.

2) Dynamic Programming Approach:

(a): Top Down Approach:

In this approach we will use memorization technique, we create a dp[] state which are initially filled with -1, each time we calculate the state we fill the dp[] state, and each time we make recursive call we first check if the value is already calculated or not, if calculate then directly return it without calculating it again and again.

(b) Bottom Up Approach:

In this approach we will fill the dp[] state in bottom up manner in the following manner.

dp[0]=1;
dp[1]=dp[2]=dp[3]=1
for other state:
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

Time Complexity for the above approach in the worst case is : O(n)

Space Complexity for the above approach in the worst case is: O(n)

C++ Implementation (Recursive Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//solve function which will return
//total ways for nth stair.
ll solve(ll n)
{
    //base case if we are at bottom.
    if (n == 0)
        return 1;
    //base case if negative stair is
    //encountered.
    if (n < 0)
        return 0;
    else //other cases as nth stair depends
        //previous three stairs as well.
        return solve(n - 1) + solve(n - 2) + solve(n - 3);
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter Nth stair: ";
        ll n;
        cin >> n;

        cout << "Total ways: ";
        cout << solve(n) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter Nth stair: 1
Total ways: 1
Enter Nth stair: 2
Total ways: 2
Enter Nth stair: 4
Total ways: 7

C++ Implementation (Dynamic Programming Approach):

(a) Top Down Approach:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//initialize dp state.
ll dp[100005];

//solve function which will return
//total ways for nth stair.
ll solve(ll n)
{
    //base case if we are at bottom.
    if (n == 0)
        return 1;
    //base case if negative stair is
    //encountered.
    if (n < 0)
        return 0;
    //check if already calculated or not.
    if (dp[n] != -1)
        return dp[n];

    //base case.
    if (n <= 2)
        return 1;

    else if (n >= 3) //other cases as nth stair depends
        //previous three stairs as well.
        return dp[n] = solve(n - 1) + solve(n - 2) + solve(n - 3);
}

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter Nth stair: ";
        ll n;
        //fill all dp state with -1 initially.
        memset(dp, -1, sizeof(dp));
        cin >> n;
        cout << "Total ways: ";
        cout << solve(n) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter Nth stair: 10
Total ways: 193
Enter Nth stair: 20
Total ways: 85525
Enter Nth stair: 30
Total ways: 37895489

(b) Bottom Up Approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter Nth stair: ";
        ll n;
        cin >> n;

        //create dp state.
        ll dp[n + 1];

        //base cases.
        dp[0] = 1;
        dp[1] = dp[2] = 1;

        //iterate through all stairs.
        for (ll i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        cout << "Total ways: ";
        cout << dp[n] << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter Nth stair: 7
Total ways: 31
Enter Nth stair: 8
Total ways: 57
Enter Nth stair: 5 
Total ways: 9

need an explanation for this answer? contact us directly to get an explanation for this answer