stairs jump

codemummy has a number of staircases in her house and she likes to climb each staircase 1 or 2 steps at a time. how many ways there are to reach the top of the staircase.

Given the respective heights for each of the  staircases in his house, find and print the number of ways he can climb each staircase.

Example:

n = 4

there are 4 steps , codemummy can take following sequence of steps:

1+1+1+1
2+2
1+2+1
2+1+1
1+1+2

There are 5 possible ways she can take these 4 steps

 Input:

1       first staircase n = 1
3       second n = 3
8       third n = 8

Sample Output

1
3
34

method 1:
using recursion.

c++ implementation:

#include<bits/stdc++.h>
using namespace std;
int c=0;
void rec(int n)
{
	if(n==1 ||n==0)
	{
		c++;
		return ;
	}
	rec(n-1);
	rec(n-2);
}
int main()
{
	int n;
	cin>>n;
	rec(n);
	cout<<c<<" ";
}

method 2:

using dynamic programming.

c++ implementation:

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

int rec(int n,int dp[])
{
    if(n==0||n==1)
    {
        dp[n]=1;
        return dp[n];
    }
    if(dp[n]==-1)
    return dp[n]=rec(n-1,dp)+rec(n-2,dp);
    else
    return dp[n];
}

int main()
{
    int n;
    cin>>n;
    int dp[n+1];
    for(int i=0;i<n+1;i++)
    dp[i]=-1;

    rec(n,dp);
    cout<<dp[n];
}