#include
#include <bits/stdc++.h>
using namespace std;
int count(int n,int m){
if(n==0){
return 0;
}
if(n<m){
return 1;
}
if(n==m){
return 2;
}
return count(n-1,m)+count(n-m,m);
}
int main() {
int t,n,m;
for(int i=0;i<t;i++){
cin>>n>>m;
cout<<count(n,m)*(10**9+7);
}
return 0;
}
hello @mansi25
10**9 works only in python.
in c++ use pow function.
u r getting tle because this recursive solution has exponentional time complexity.
use dynamic programming to make it efficient
concepts of dynamic are yet to be covered in series so how can we apply that
leave this for now , try it again after learning dp.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
still i am not able to solve this
…
use a single array to memoise the result
can u send mw solution plz
pls refer this ->
int dp[100001]; //initialise it with -1
int f(int n, int m)
{
if (n < m) return dp[n] = 1;
if (dp[n] != -1) return dp[n];
return dp[n] = (f(n - 1, m)%1000000007 + f(n - m, m)%1000000007)%1000000007; //apply modulo here to avoid overfow
}still tle error is comming
check now->