I believe this question is based on the recursion and not on dp, then why i am getting TLE?

#1

this is my solution!

int tilingProb(int n, int m) {
//Base Case
if(n == 0) {
return 1;
}
if(n < 0) {
return 0;
}

//recursive calls
int ans1 = tilingProb(n-m, m);
int ans2 = tilingProb(n-1, m);
return (ans1 + ans2)%1000000007;

}

int main() {
int t;
cin >> t;

while(t--) {
	int n, m;
	cin >> n >> m;
	
	int res = tilingProb(n, m);
	cout << res << endl;
}

}

#2

Hi @alter
this problem is based on dp. u will find that relation will be of the form dp[n]=dp[n-m] + dp[n-1];
if u dont use dp, because of overlapping subproblems u will get tle.
Hope dis helps.
u can refer to this code for more help.

#3

if this is dp problem, then why it is being put in recursion section and not in dp section? I do not know dp at present!

#4

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.