T(n,k) = 1 when n<=k

T(n,k) = T(n-1,k)+T(n-2,k)+T(n-3,k)+…+T(n-k,k) when n>k

my observation T(5,2) = 5
T(7,5) = 9
T(6,2) = 8
T(8,3) = 31
please provide some clue to solve this problem ?

Hello @k_purushottam,
If n < k, then just print 1
Else
We know that dp[i] will be the sum of last k terms.

``````	dp[i] = dp[i-1] + dp[i-2]...+dp[i-k] % MOD.
``````

So this can be done by sliding window algorithm.

My code :

``````#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define vii vector<ll>
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7, N = 1e4 + 3;

int main(){
fast;
ll n, k;
cin >> n >> k;
if(n < k) cout << 1;
else{
ll dp[n];
for(int i = 0; i < k; ++i) dp[i] = 1;
int sum = k;
for(int i = k; i < n; ++i){
dp[i] = sum;
sum = (sum + dp[i]) % MOD;
sum = (sum - dp[i-k]) % MOD;
}
cout << dp[n-1];
}
cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
return 0;
}
``````

I hope you understood it

2 Likes

thanks for the help