TILLING PROBLEM 2

#1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll tilling2(ll m,ll n)
{
if(m<=0 || n<=0)
{
return 0;
}
if(m<n)
{
return 1;
}
if(n==m)
{
return 2;
}
if(m>n)
{
return tilling2(m-1,n)+tilling2(m-n,n);
}
}
int main()
{
// let’s play
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t–)
{
ll n,m;
cin>> n>> m;
ll ans=tilling2(n,m);
cout<<ans<<endl;
}
}

#2

it gives error of tle

#3

please reply as early as possible

#4

hello @sunneykumar309
use dynamic programming to pass all test cases.

recusive solution has exponential time complexity , thats why it is giving tle

#5

ok @aman212yadav but i have not studied yet those topics

#6

ok try this problem after studying dp.
we dont have any other solution to improve its time complexity.

1 Like
#7

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.

#8

#include <bits/stdc++.h> using namespace std; int countWays(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]; else if (i < m || i == 1) count[i] = 1; else count[i] = 2; } return count[n]; } int main() { int t; cin>> t; while(t–) { int n,m; cin>> n>> m; cout << countWays(n, m)<<endl; } return 0; }

#9
#10

i am using dp here but i am getting wrong answer

#11

hello @sunneykumar309 wait i will go through your code and let you know the error .

1 Like
#12

hello @sunneykumar309 see i have corrected your code and now it is passing every test case .

#13

ok …

#14

hey @sunneykumar309 if you feel that your doubt is cleared please mark this doubt as resolved .

#15

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.