Tilling timelimit in 3 cases

#1

Please help

#2

Hi @shivansh.sm1
You are facing TLE because you are using recursion and this problem contains a lots of over lapping sub problems. Instead you should use dp to solve this question.

Approach: For a given value of n and m, the number of ways to tile the floor can be obtained from the following relation.

count(n) = 1, 1 < = n < m
count(n) = 2, n = m
count(n) = count(n-1) + count(n-m), m < n

If your doubt is clear then mark it as resolved.

#3

@Aayush

#include<iostream>
using namespace std;
int countWays(int n,int m){
	int i,count[10000]={0};
	count[0]=0;
	for(i=1;i<=n;i++){
		if(i<m)
		{
			count[i]=1;
		}
		if(i==m){
			count[i]=2;
		}
		if(i>m){
			count[i]=count[n-i]+count[n-1];
		}
	}
	return count[n];
}
int main() {
	int t,n,m;
	cin>>t;
	while(t--){
		cin>>n>>m;
		cout<<countWays(n,m)<<endl;
	}
	return 0;
}

This is giving run error.pls help

#4

@shivansh.sm1
Run error is because m,n<=100000 so count as count[100001] and also when i>m then it should be
count[i]=(count[i-1]+count[i-m])%1000000007;
Here %1000000007 is must because answer could be large and also it is mentioned in the question that
“Print answer for every test case in a new line modulo 10^9+7.”

Here is your corrected code :

If your doubt is clear then mark it as resolved.