Solution : Count ways to reach the n'th stair | Dynamic programming | geeksforgeeks

 There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does matter).

Example 1:

Input:
n = 4
Output: 5
Explanation:
You can reach 4th stair in 5 ways. 
Way 1: Climb 2 stairs at a time. 
Way 2: Climb 1 stair at a time.
Way 3: Climb 2 stairs, then 1 stair
and then 1 stair.
Way 4: Climb 1 stair, then 2 stairs
then 1 stair.
Way 5: Climb 1 stair, then 1 stair and
then 2 stairs.

Example 2:

Input:
n = 10
Output: 89 
Explanation: 
There are 89 ways to reach the 10th stair.

Your Task:
Complete the function countWays() which takes the top stair number m as input parameters and returns the answer % 10^9+7.

Expected Time Complexity : O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ n ≤ 104

solution :

 

In this solution , i have fibbonacci approach.

The function int count() is the solution of fibbonacci series using memoization methord of dynamic programming.

class Solution

{

    public:

    //Function to count number of ways to reach the nth stair.

    long long int t = 10e9 +7;

    int count(int n , int dp[])

    {

        if(n <=1)

        return dp[n] =1;

        else

        if( dp[n] != -1)

         return dp[n] ;

        else

         dp[n] = (count(n-1 , dp) + count(n-2 , dp))%1000000007;

         return dp[n] ;

    }

    int countWays(int n)

    {    

        int dp[n+1] ;

        memset(dp , -1 , sizeof (dp));

        count(n , dp);

        return dp[n] %1000000007 ;

        

        

    }

};