PROG-1079: หม้อวิเศษ (pot)

#include <bits/stdc++.h>
using namespace std;
int n,k;
int dp[100001],qs[100001];
int main(){
    scanf("%d %d",&n,&k);
    dp[0]=1;
    qs[0]=1;
    for(int i=1;i<=n;i++){
        if(i<=k)//base case for dp and qs
            dp[i]=qs[i-1];
        else
            dp[i]=qs[i-1]-qs[i-k-1];

        dp[i]=dp[i]%2009;
        qs[i]=qs[i-1]+dp[i];
    }
    printf("%d",dp[n]);

    return 0;
}