question–>
https://practice.geeksforgeeks.org/problems/count-number-of-hops-1587115620/1#
code–>
help i cannot find out recursive?
Count number of hops
hello @sheikhhaji18
check now->
reccurence relation is ->
ways(n)=ways(n-1) + ways(n-2) +ways(n-3)
base case : n==0 return 1.
now apply top down dp to optimise the complexity.
also it is asked to take mod of ur answer so take care of that as well
it is 1D dp right because it depends on n only
yes. . . . . . . . .
long long int fun(long long int n,int dp[]){
if(n==0 ){
dp[n]=1;
return 1;
}
if(n<0){
return 0;
}
if(dp[n]!=-1){
return dp[n];
}
long long int ans1=fun(n-1,dp)%100000007;
long long int ans2=fun(n-2,dp)%100000007;
long long int ans3=fun(n-3,dp)%100000007;
dp[n]= (ans1+ans2+ans3)%100000007;
return dp[n];
}
long long countWays(int n){
long long int dp[10001]={0};
for(int i=0;i<10001;i++){
dp[i]=-1;
}
long long int ans=fun(n,dp);
return ans;
}
what is wrong it is not passing all testcases?@aman212yadav r u there? bottom up is working fine but top down is working
check now->
value of mod was incorrect. (u were using 7 0’s)
no still it is not submiting ,but this is like fibonacci and the ladder problem
