[Codeforces] C. k-Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C. k-Tree
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : Basic Dynamic Programing
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 100 + 5;  
static const int mod = (int)1e9+7;  
  
int add(int a, int b)  
{  
      a += b;  
      if (a >= mod) a -= mod;  
      return a;  
}  
  
int dp[maxn][2];  
bool memoize[maxn][2];  
int n, k, d;  
  
int solve(int sum = 0, bool flag = 0)  
{  
      if (sum == n) return flag;  
      if (sum > n) return 0;  
      int &ret = dp[sum][flag];  
      bool &mem = memoize[sum][flag];  
      if (mem) return ret;  
      mem = 1;  
      ret = 0;  
      for (int weight = 1; weight <= k; weight++)  
      {  
            ret = add(ret, solve(sum + weight, flag | weight >= d));  
      }  
      return ret;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> k >> d;  
      cout << solve(0, 0) << '\n';  
}