Tile question:Given a floor of size n x m. Find the number of ways to tile the floor with tiles of size 1 x m . A tile can either be placed horizontally or vertically

#1

Input Format
First line of input contains an integer T denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two integers N and M.

I wanted to know how to do this using recursion as the editorial was not a recursive approach.
Thanks

#2

Recursive function for this problem should be something like this:
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;
}

However just by recursion, your code will not pass all the test cases and will give Time Limit Exceed error since the constraints are large. You need dynamic programming to solve this problem. So i would suggest you to attempt this problem after completing Dynamic Programming concepts.

1 Like
#3

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.

#4

Here is the memoization approach.

#include <bits/stdc++.h>
#define ll long long int

using namespace std;

ll mod = 1e9+7;

ll dp[1000000];

ll find(ll n,ll m)
{
if(n==0) return 1;
if(n<0) return 0;

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

ll way1 = find(n-1,m)%mod;
ll way2 = find(n-m,m)%mod;
return dp[n] = (way1+way2)%mod;

}

int main() {

int t;
cin>>t;

while(t-->0)
{
	ll n,m;
	cin>>n>>m;
    memset(dp,-1,1000000);
	cout<<find(n,m)<<endl;
}

return 0;

}