What should be the correct logic for the question Tiling Problem -II.
Code-
#include
using namespace std;
int dp[100001]={0};
int findways(int n , int m)
{
if(dp[n]!=-1)
{
return dp[n];
}
if(n<1)
{
dp[n]=0;
return dp[n];
}
if(n==m)
{
dp[n]=2;
return dp[n];
}
if(n<m)
{
dp[n]=1;
return dp[n];
}
//recursive case
dp[n]= (findways(n-1,m)+ findways(n-m,m));
return dp[n];
}
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
for(int i=0;i<100001;i++)
dp[i]=-1;
cout<<findways(n,m)%(1000000000+7)<<endl;
}
return 0;
}