Please help me to solve K Fibonnachi . ( problem link in description )

general
1

problem link KFIB Problem - CodeChef

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 ?

2

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 :slightly_smiling_face:

2 Likes
3

thanks for the help :grinning: