my solution is not working for large input of n and m
code:
#include
using namespace std;
typedef long long ll;
ll N=1000000007;
ll tilling(ll n,ll m){
if (m>n && n>=1) return 1;
else if (n<=0) return 0;
else if (m==n) return 2;
else return (tilling(n-1,m)%N+tilling(n-m,m)%n);
}
int main() {
ll t;
cin>>t;
while (t–){
ll n,m;
cin>>n>>m;
cout<<tilling(n,m)%(N)<<endl;
}
return 0;
}
Hello @sandeep021,
As you have pointed out that this program is not working for large values.
Yes, that is correct.
The backtracking approach would cause TLE for large input.
To eliminate TLE, you are required to use the DP i.e. Dynamic Programming Approach to solve this problem.
Thus, I would suggest you to solve this problem after completing DP.
Hope, this would help.
Give a like if you are satisfied.
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.