Advertisement
jayati

Count number of hops

Dec 3rd, 2023
807
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. //{ Driver Code Starts
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // } Driver Code Ends
  6.  
  7. class Solution
  8. {
  9.     public:
  10.     //Function to count the number of ways in which frog can reach the top.
  11.     long long countWays(int n)
  12.     {
  13.           int mod = 1000000007;
  14.         long long dp[n+1];
  15.         dp[0] = 1;
  16.        
  17.         for(int i=1;i<n+1;i++)
  18.             dp[i] = 0;
  19.            
  20.         for(int i=1;i<n+1;i++){
  21.             dp[i] += dp[i-1]%mod;
  22.            
  23.             if(i>1)
  24.                 dp[i] += dp[i-2]%mod;
  25.             if(i>2)
  26.                 dp[i] += dp[i-3]%mod;
  27.         }
  28.         return dp[n]%mod;
  29.        
  30.     }
  31. };
  32.  
  33.  
  34. //{ Driver Code Starts.
  35. int main()
  36. {
  37.     //taking testcases
  38.     int t;
  39.     cin >> t;
  40.    
  41.     while(t--)
  42.     {
  43.         //taking number of steps in stair
  44.         int n;
  45.         cin>>n;
  46.         Solution ob;
  47.         //calling function countWays()
  48.         cout << ob.countWays(n) << endl;
  49.     }
  50.    
  51.     return 0;
  52.    
  53. }
  54.  
  55. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement