Codeforces 431C - k-Tree Solution

 #include <bits/stdc++.h>
using namespace std;
int mod=1000000007;
int s,k,d;
vector<vector<int> > dp;
int rec(int sum,int dd){
    if(sum<0)return 0;
    if(dp[sum][dd]!=-1)return dp[sum][dd];
    int ret=0;
    for(int i=1;i<=k;i++){
        if(i<dd){
            ret+=rec(sum-i,dd);
            ret=ret%mod;
        }
        else{
            ret+=rec(sum-i,0);
            ret=ret%mod;
        }
    }
    return dp[sum][dd]=ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s>>k>>d;
    dp.assign(s+1,vector<int>(d+1,-1));
    for(int i=0;i<=s;i++){
        for(int j=i+1;j<=d&&j<=s;j++)
            dp[i][j]=0;
    }
    for(int dd=1;dd<=d&&dd<=s;dd++)
        dp[dd][dd]=1;
    dp[0][0]=1;
    cout<<rec(s,d);
    return 0;
}