Tiling problem -2

#1


what modifications are required?

#2

@Vibhuti0206
The constraints mentioned in this problem are a bit tight and hence you will not be able to solve this problem completely using just recursion. You need to optimise your approach , which is where Dynammic Programming comes in. Try optimising your solution using DP. If you have only covered the recursion section and not reached till DP in your course , I suggest you to leave this problem for now and come back to it when you cover DP. Since your recursive approach seems right , you have already got the most part . Adding Memoization ( DP technique ) to your code would be easy for you later.

1 Like
#3 
#include<bits/stdc++.h>
#include<vector>
#include<iostream>
using namespace std;
#define ll long long
ll mod = 1e9 + 7;
long long func(int n,int m)
{
    vector<ll> dp(n+1, 0);
    dp[0]=0, dp[1]=1;
    for(ll i=2; i<=n; i++)
    {
        dp[i] = dp[i-1];
        if(i-m>0)
            dp[i] += dp[i-m];
        else if(i==m)
            dp[i] = 2;
        dp[i] %= mod;
    }
    return dp[n];
}


int main() {
    int t; cin>>t;
    while(t--){
    int n,m; cin>>n>>m;
    cout<<func(n,m)<<endl;
    }
	return 0;
}