Given a floor of size n x m. Find the number of ways to tile the floor with tiles of size 1 x m . Print answer for every test case in a new line modulo 10^9+7.
I am facing time limit exceeded issue in this question for 4 test cases. How can this issue be resolved?
Here is the link to my code: https://ide.codingblocks.com/s/74304
I have not yet reached dynamic programming topics in the course, so find it a little difficult to implement the solution using DP. The algorithm which I could think of was to first find the maximum no. htile_max of horizontal tiles that can be placed and then using Combinations in a loop(run for htile_max times), but I am not able to implement it in the program.
Can you please suggest improvements in my recursion code to eliminate time limit exceeded problem. Am I outputting the result correctly while doing result modulo 10^9+7 in the function numWays()?
@Megha hey megha this question is solved using dynamic programming and dynamic programming is of two type first top down dp which is also called as memoization and second type is bottom up dp and it is also know as tabulation method and it is faster than memoization and bottom up dp is consider as pure dp
so let us discuss bottom up dp
long long int count[n+1];
count[0]=0;
for(int i=1;i<=n;i++){
//recurrence result
if(i>m){
count[i]=(count[i-1]+count[i-m])%MOD;
}
else if(i<m)
count[i]=1;
else
count[i]=2;
}
return (count[n])%MOD;
}
hope this help you
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.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl “\n”
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define input freopen(“Test.txt”,“r”,stdin)
#define output freopen(“Output.txt”,“w”,stdout);
#define what_is(x) cout<<#x<<" is "<<x<<endl;
#define pb push_back
#define eb emplace_back
#define inf 1000000000
const double pi = 3.141592653589793238460;
#define mod 1000000007
//iterative
int count1(int n,int m)
{
int count[n+1];
count[0] = 0;
for(int i=1;i<=n;i++)
{
if(i>m)
count[i] = (count[i-1]+count[i-m])%mod;
else if(i==m)
count[i] = 2;
else
count[i] = 1;
}
return count[n];
}
//recursive
int count2(int n,int m)
{
if(n<=0)
return 0;
else if(n>=1 and n<m)
return 1;
else if(n==m)
return 2;
else
return (count1(n-1,m)+count1(n-m,m))%mod;
}
int main()
{
fast_io;
///input;
///output;
int T;
cin>>T;
while(T–)
{
int n,m;
cin>>n>>m;
int ans = count1(n,m);
cout<<ans<<endl;
}
return 0;
}
It is not fair though that this problem gives TLE with recursive approach as the problem itself is placed under the recursion bucket, atleast in some courses!