Why is iterative code passing but recursive is not , I am not able to find the difference .Both will be O(n) . Is it because of stack overflow issue because n,m values are large. I am not able to find out because test cases are hidden . The error thrown in recursive code is “Run Error”. Please explain. If I can get any recursive solution code for this question and the constraints given It would help me a lot. Or this question needs an iterative solution to pass all test cases.
Tiling Problem - II
hi @Prakarsh time complexity of recursion is really high, so you need to use DP in this case for optimization.
Yes , I did using top down approach but seems to not pass all test cases but bottom up (iterative) approach works well. I was asking is it due to constraints of the problem .If any recursive(top down) solution possible then please share
@Prakarsh you’ll have to use memoization with the top down approach. It passes all the test cases with recursion + memoization.
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long int ll;
ll f(vector &dp,ll n,ll m)
{
if(n<0)
return 0;
if(dp[n]!=-1)
return dp[n]%mod;
else
dp[n]=(f(dp,n-1,m)%mod+f(dp,n-m,m)%mod)%mod;
return dp[n]%mod;
}
int main() {
int t;
cin>>t;
while(t–){
ll n,m;
cin>>n>>m;
vector dp(n+1,-1);
dp[0]=0;
for(int i=1;i<m;i++)
dp[i]=1;
dp[m]=2;
cout<<f(dp,n,m)<<endl;
}
return 0;
}
This is my top down approach code but only test case 3 passes . I have tried with custom inputs and they give correct answers as per my understanding. May my code be reviewed it ll be of great help.
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.