#include<bits/stdc++.h>
using namespace std;
int tiling(int n,int m)
{
if(n<=m-1)
return 0;
return tiling(n,m)+tiling(n-m,m)+1;
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
int res=tiling(n,m);
int a=pow(10,9)+7;
res=res%a;
cout<<res<<"\n";
}
return 0;
}
why this code is not giving correct answer
@rupeshjha909 Recursive function for this problem should be something like this:
int noofways(int n,int m)
{
if(n==0)
return 1;
if(n<0)
return 0;
int way1=noofways(n-1,m);
int way2=noofways(n-m,m);
return (way1+way2)%1000000007;
}
However just by recursion, your code will not pass all the test cases and will give Time Limit Exceed error since the constraints are large. You need dynamic programming to solve this problem. So i would suggest you to attempt this problem after completing Dynamic Programming concepts.
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.