question: tilling problem
#include
using namespace std;
long long int cal(int n,int m,int tile){
long long sum1 = n>=1? 1 + cal(n-tile,m-1,tile):0;//placing column wise
long long sum2 = m>=tile?1 + cal(n-1,m,tile):0;//placing row wise
return sum1+sum2;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
cout<<cal(n,m,m);
}
}
Hi @siddharth9k9
The recurrence relation that you have used here is not correct. The recurrence relation here should be:
count(n) = {
1, 1 < = n < m ,
2, n = m ,
count(n-1) + count(n-m), m < n
}
Here is your code with correct recursive solution :
But this code will produce TLE, so try to think of DP approach for this question then you will pass all the test cases.
If your doubt is clear then mark it as resolved.
your code gives tle when i try to submit
@siddharth9k9
As i mentioned earlier this code will give TLE, so you need to think of dp approach to get rid of TLE and pass all the test cases.