GOT TLE in spite of using recursion

#1

I used recursion to solve the problem, but still got TLE. Please check where I went wrong

#2

hello @kartiksinghal0611
the recursive solution has exponential time complexity thats why u r getting tle .

so to improve the time complexity use dynamic programming

#3

haven’t study dp yet

#4

ok then leave it for now,try after studying dp

#5

#include
using namespace std;
#define mod 1000000007

int no (int n , int m){
if(n<m){
return 1;
}
int a = (no(n-1,m))%mod;
int b= (no(n-m,m))%mod;
return ((a+b)%mod);

}

int main(){
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
cout<<no(n,m)<<endl;
}

}

#6

This code won’t work?

#7

no … …

#8

okay, thanks for guiding

#9

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.