I am getting run error for this problem. Only one test case passes correctly. I checked the solution provided but not able to understand.
Getting run error
1 Like
You have to use dynamic programming in this question. Your recursion approach is correct but since the test cases are large it will run out of memory and throw a run error.
I hope that was getting correct! and should have passed all the test cases!
If you have no further doubts " mark it as resolved";
thanks
use (int)Math.pow(10,9) + 7 instead of 10^9+7
I tried this but now working!!
@mr.dheeraj000,
I can’t provide you the code. What I can suggest is that you first go through the dynamic programming section and then come back to solve this question. Or you can give it a try without using recursion, I will help you out in case you are not able to understand 
okay! Let me try first.
DP is easy when you have formalized the problem
In this case formalized formula is f(n) = f(n-1) + f(n-m)
So,
- Declare an array of size n, let say dp[n] (if 1 -indexed)
- From dp[1] to dp[m-1] initiate dp[i] =1
- From dp[m] to dp[n] formulate dp[n]=dp[n-1] + dp[n-m]
Print dp[n]
Note: be cautious if n is less than m, in that case just return 1
import java.util.*;
public class Main {
public static int findwaytotiles(int n , int m)
{
if(n<m)
return 1;
int[] dp=new int[n+1];
for(int i=0;i<m;i++)
{ dp[i]=1;
}
for(int i=m ;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-m];
dp[i]=dp[i]%1000000007;
}
return dp[n];
}
public static void main(String args[]) {
Scanner sc= new Scanner(System.in);
int test= sc.nextInt();
while(test>0)
{
int n=sc.nextInt();
int m =sc.nextInt();
int result=findwaytotiles(n , m);
System.out.println(result);
test--;
}
}
}
I tried this and it worked thanks @rkrishna @sanchit.bansal06 