Ques . A monkey hops one, two or three steps at a time. (Only forward jumps).

Starting from step number 0, in how many ways can it reach the step number n ?

1<=n<=10^5

 

Recursive equation →    F[n]=F[n-1]+F[n-2]+F[n-3]

 

Top Down Approach

 

int dp[100];

int solve (int x){

   if (x<=1)

   return 1;

   if (x==2)

   return 2;

   if (dp[x]!=-1){ // if (~dp[x]) also //works, think why

    return dp[x];

   }

   int ans = solve(x-1)+solve(x-2)+solve(x-3);

   dp[x]=ans;      // this step is for memoization. As already discussed, once we have calculated           the answer for a particular 'x', we don't want to recompute it.

   return ans;

}

 

int main(){

   int n;

   // we can also use memset in string.h

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

   cin>>n; // read n;

   cout<<"The number of ways is ::"<<solve(n);

   return 0;

 

}

Bottom up Approach

 

int i;

F[0]=1;

F[1]=1;

F[2]=2;

for (i=3;i<=n;i++){

   F[i]=F[i-1]+F[i-2]+F[i-3];

}