Tilling Problem - II using recursion we have to place 1*m tiles on n*m block

#1

i am getting tle for 4 test cases , can u tell me the optimizations , here is my code:-

#include
using namespace std;

#define M 1000000007

int ways(int m,int n){
if(n<=3)
return 1;
else if(n==4)
return 2;

return ways(m,n-1)+ways(m,n-4);
}

int main() {

int t,m,n;
cin>>t;

while(t–){
cin>>n;
cin>>m;
cout<<ways(m,n)%M<<endl;

}

return 0;

}

#2

Try dynamic Programming.
please post the question link.

#3

Question link is https://hack.codingblocks.com/contests/c/537/1045
now i have done DP but it is still showing error , please check my code:-

#include
using namespace std;

#define M 1000000007
long int memo[100000];

long int ways(long int m,long int n){
if(n<=0)
return 0;
if(n<m&&n>=1)
return 1;
else if(n==m)
return 2;

if(memo[n]!=-1)
return memo[n];

long int ans = ways(m,n-1)%M +ways(m,n-4)%M;
memo[n] = ans;
return ans;
}

int main() {

int t;
long int m,n;
cin>>t;

while(t–){
cin>>n;
cin>>m;
for(long int i=0;i<=n;i++){
memo[i] = -1;
}
cout<<ways(m,n)<<endl;
}

return 0;
}

#4

Your code has various errors
first : it is going infinite loop because of recursion, you have incorrectly written memoization. Checking memo[n] and calling for n-1 and n-4;

second : your DP is wrong, try again by forming a correct recursion and then convert it into dp.
you recursion if wrong.
try to analyse the what will be the first step and then do a recursive call on rest of the filling area.

try once again if you can’t resolve , comment i’ll post the exact solution.
Cheers! Happy coding!

#5

thanks i have corrected it btw the only recursive call was wrong in my code but the memoization that i have done was right.