Tiling Problem- II

#1

link of question https://hack.codingblocks.com/contests/c/547/1045

i have used the recursive approach: f(n,m)=f(n-1,m)+f(n-m,m)…i have took the base case that if n=0 return 1 and if n<0 return 0.
Sample input and only Test Case 4 is passing, Rest all test cases are giving time limit exceed… How to optimize? Please explain

#include
using namespace std;
int noofways(int,int);
int main() {
int t,n,m;
cin>>t;
while(t–)
{
cin>>n>>m;
int count=noofways(n,m);
cout<<count<<endl;
}
return 0;
}
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;
}

#2

Hey Pratyush, you are getting TLE as the constraints for M and N are large, to try to optimize your code using dynamic programming. You can refer this pseudo code

vector<ll>dp(n+1,0);
    dp[0]=1ll;
    for(ll i=1;i<=n;i++){
      // Placing the tile vertically
      dp[i]=dp[i-1];
      // Placing the tile horizontally if there is space
      dp[i]+=((i-m)>=0)?dp[i-m]:0; 
      dp[i]%=(1e9 + 7);
    }
    print (dp[n]);
#3

Hey Pratyush, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

1 Like