Getting TLE in testcases

#1

#include

using namespace std;

int tiles(int *dp, int n, int m){

if(n<0){
	return 0;
}

if(n<m){
	return 1;
}

if(dp[n]!=0){
	return dp[n];
}

return tiles(dp,n-1,m)+tiles(dp,n-m,m);

}

int main(){

	int t;

	cin>>t;

	while(t--){

	int dp[100000]={0};

	int n;
	cin>>n;

	int m;
	cin>>m;

	cout<<tiles(dp,n,m)<<endl;

}



return 0;

}

#2

there are 2 small mistakes in your code

  1. you need to assign dp[n] before you return sum of tiles(n-1) and tiles(n-m)
  2. you need to take modulo as mentioned in the question
    Corrected Code
    https://ide.codingblocks.com/s/293968
1 Like
#3

#include

using namespace std;

int tiles(int *dp, int n, int m){

if(n<0){
	return 0;
}

if(n<m){
	return 1;
}

if(dp[n]!=0){

	return dp[n];
}

dp[n-1]=tiles(dp,n-1,m);
dp[n-m]=tiles(dp,n-m,m);

return dp[n-1]+dp[n-m];

}

int main(){

	int t;

	cin>>t;

	while(t--){

	int dp[100]={0};

	int n;
	cin>>n;

	int m;
	cin>>m;

	cout<<tiles(dp,n,m)<<endl;

}



return 0;

}

#4

Why is this still wrong @keshavgupta0103?

#5

i have provided you with the corrected code please look at it.

#6

return dp[n-1]+dp[n-m];
Be replaced with
return dp[n]=dp[n-1]+dp[n-m];

#7

@rkrishna
#include

using namespace std;

const int mod=1e9+7;

int tiles(int *dp, int n, int m){

if(n<0){
	return 0;
}

if(n<m){
	return 1;
}

if(dp[n]!=0){

	return dp[n];
}

dp[n-1]=tiles(dp,n-1,m);
dp[n-m]=tiles(dp,n-m,m);

return dp[n]=(dp[n-1]+dp[n-m])%mod;

}

int main(){

	int t;

	cin>>t;

	while(t--){

	int dp[100]={0};

	int n;
	cin>>n;

	int m;
	cin>>m;

	cout<<tiles(dp,n,m)<<endl;

}



return 0;

}

#8

Still is giving problems. @keshavgupta0103 I understood your code, just trying to catch my mistake here please help.

#9

int dp[100]={0};
why this,
n may be bigger!!

#10

increase the size of dp to 100000

#11

Thank you both, corrected!

#12

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.