# Stair Case: C++ program to solve the staircase problem

Here, we are going to implement a C++ program to solve the staircase problem.
Submitted by Indrajeet Das, on December 14, 2018

A child is running up a staircase with N steps, and can hop 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs? You need to return number of possible ways W.

Input format: Line 1: Integer N (No. of steps)

Output Format: Line 1: Integer W i.e. Number of possible ways

Constraint: (1 <= N <= 30)

Sample Input 1: 4

Sample Output: 7

Explanation:

In this question, to find out the number of ways to we can climb the stairs, we can use a recursive method to solve it. We can call the recursive function thrice in our code with parameters of (N-1), (N-2) and (N-3) steps (the decrease in steps show the number of steps climbed). And add and return them.

It is one of the typical questions for recursive algorithms.

Algorithm:

1. Step 1: Declare a recursive function staircase with one parameter (int steps).
2. Step 2: Base Case:
if(steps <0) // No steps to climb
return 0;
3. Step 3: Base Case 2:
if(steps ==0) //Already reached top
return 1;
4. Step 4: Return staircase (steps -1) + staircase (steps – 2) + staircase (steps -3).
i.e. the total ways in which we can climb the steps.

Example:

```    For stairs = 3.
Ways to climb are,
1 1 1
1 2
2 1
3
Hence there are four ways to climb.
```

C++ program:

```#include<bits/stdc++.h>

using namespace std;

//Recursive Function
int staircase(int n){
if(n<0){            //Base Case 1
return 0;
}

if(n==0){           //Base Case 2
return 1;
}

int count = 0;
count += staircase(n-1);    //Stepping 1 step
count += staircase(n-2);    //Stepping 2 step
count += staircase(n-3);    //Stepping 3 step

return count;
}

//Main
int main(){
int n;
cout<<"Enter number of stairs"<<endl;
cin>>n;

cout<<"No of ways to climb stairs are ";
cout<<staircase(n)<<endl;

return 0;

}
```

Output

```Enter number of stairs
5
No of ways to climb stairs are 13
```

TOP Interview Coding Problems/Challenges

Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.