Time Limit Exceeded for many test Cases Tiling -2

#1

Can you explain how can I optimize this code?And also if this code is correct or not?

#2

hi himanshu
can you please provide your code by saving it on the online ide

#3

this is the code please tell me what’s wrong?
#include<bits/stdc++.h>
using namespace std;
int tiling(int n,int m ){
if(n<=m-1){
return 1;
}
if(n>=m){
return tiling(n-1,m)+tiling(n-m,m);

}

}
int main() {
int t;
cin>>t;
for(int i=0;i<t;i++){
int n,m;
cin>>n>>m;
cout<<tiling(n,m)%1000000007<<endl;

}

return 0;

}

#4

yes your code is correct
you can optimize it by using dynamic programming approach
| 1, 1 < = n < m
count(n) = | 2, n = m
| count(n-1) + count(n-m), m < n
store answer for every point
create count[n+1]
initialize count[0]=1;
then find the answers for remaining indexes of count
and at the end return count[n]

#5

But this question is in recursion topic of my assignment so I have to do it recursively right? Or will it accept the DP solution?

#6

it will accept the solution in dp as well

#7

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.