I am getting TLE, please help!

#1

#include
using namespace std;

int fillIt(int a,int b)
{
if(a<b)
return 1;
return fillIt(a-1,b)+fillIt(a-b,b);

}

int main() {
int t;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
cout<<fillIt(a,b)<<endl;
}
return 0;
}

I wrote this and getting TLE. I optimised the code too

#include
using namespace std;

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

int main() {
int t;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
cout<<fillIt(a,b)<<endl;
}
return 0;
}

But this still doesnt works.

#2

hello @haseebshaik00

ur recursive solution has exponential time complexity thats why it is giving tle

use dynamic programming to optimise ur solution

#3

I dont know dp as of now, isn’t there any other way to do?

#4

no , skip this problem for now,try after learning dp

#5

ok thank you bhaiya!