« How many possible ways the child can run up to the staircase

Problem

A child is running up a staircase with N steps, and can hop either 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 :

Integer N

Output Format :

Integer W

Constraints :

1 <= N <= 30

Sample Input 1 :

4

Sample Output 1 :

7

Sample Input 2 :

5

Sample Output 2 :

13

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int staircase(int n)
15{
16    if (n == 0)
17    {
18        return 1;
19    }
20    if (n < 0)
21    {
22        return 0;
23    }
24    return staircase(n - 1) + staircase(n - 2) + staircase(n - 3);
25}
26
27int main()
28{
29    int n, output;
30    cin >> n;
31    output = staircase(n);
32    cout << output << endl;
33    return 0;
34}