A frog jumps either 1, 2, or 3 steps to go to the top. In how many ways can it reach the top. As the answer will be large find the answer modulo 1000000007.
Eg
N = 4
Output: 7
Explanation:Below are the 7 ways to reach
4
1 step + 1 step + 1 step + 1 step
1 step + 2 step + 1 step
2 step + 1 step + 1 step
1 step + 1 step + 2 step
2 step + 2 step
3 step + 1 step
1 step + 3 stepApproach :
- Similar to climbing stairs problem here on leetocde
- Just start from the given "N" and you can decrement N either by N-1 / N-2 / N-2
- Base cases are :
if(n==0) return 0; // 0=0
if(n==1) return 1; // 1=1
if(n==2) return 2; // 2=1 +1 or 2
if(n==3) return 4; // 2= 1+1+1 or 1+2 or 2+1 or 3Recurive Code (Time Compelxity is O(3^N) & space is O(1) )
long long countWays(int n)
{
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
return (countWays(n-1) + countWays(n-2) + countWays(n-3)) %1000000007;
}Memoization (Time Compelxity is O(N) & space is O(N) )
long long solve(int n,vector<long long> &dp)
{
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
if(dp[n]!=-1) return dp[n];
return dp[n]=(solve(n-1,dp) + solve(n-2,dp) + solve(n-3,dp))%1000000007;
}
long long countWays(int n)
{
vector<long long> dp(n+1,-1);
return solve(n,dp);
}Pure DP (Time Compelxity is O(N) & space is O(N) )
long long countWays(int n)
{
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
vector<long long> dp(n+1);
dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4;
for(int i=4;i<=n;i++)
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007;
return (dp[n])%1000000007;
}Most Optimal Solution (Time Compelxity is O(N) & space is O(1) )
Approach
- Instead of using array of size n+1 we can use array of size 3 because for calculating no of ways for a particular step we need only last 3 steps no of ways.
- For each index compute the value as ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3] and store its value at i%3 index of array ways. If we are computing value for index 3 then the computed value will go at index 0 because for larger indices(4 ,5,6…..) we don’t need the value of index 0.
int countWays(int N)
{
//Create the array of size 3.
int ways[3] , n = N;
//Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
//Run a loop from 3 to n
//Bottom up approach to fill the array
for(int i=3 ;i<=n ;i++)
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
return ways[n%3];
}Comments (1)