Tiling Problem-II

#1

I am getting TLE in all the test cases except one:
what is the error in the code, I couldn’t identify.

#include<bits/stdc++.h>

using namespace std;

long int tile(long int n,long int m)
{

if(n==0)
{
	return 0;
}
if(n<m||n==1)
{
	return 1;
}
if(n==m)
{
	return 2;
}
return tile(n-1,m)+tile(n-m,m);

}

int main()
{

int t;
cin>>t;
while(t--)
{
	long int n,m;
	cin>>n>>m;
	long int ans=tile(n,m);
	cout<<ans<<"\n";
}

}

#2

hello @lakshyatoshniwal
your recursive solution is correct .

to optimise it furthur use dynamic programming.

#3

I am still getting TLE:

#4

pls share ur dp code

#5

I am still getting TLE: …Here is the implementation: #include<bits/stdc++.h> using namespace std; #define mod 1000000007 int main() { int t; cin>>t; while(t–) { long int n,m; cin>>n>>m; long int dp[n+1]; dp[0]=0; for(int i=1;i<m;i++) { dp[i]=1; } dp[m]=2; for(long int i=m+1;i<=n;i++) { dp[i]=(dp[i-m]%mod+dp[i-1]%mod)%mod; } cout<<dp[n]%mod<<"\n"; } }

#6

save it here-> https://ide.codingblocks.com/
and then share the link

#7

Not able to generate coding blocks IDE link. How to share??

#8
#9

your code is correct pls try after sometime…