I am new at CP, and have only given one contest Can someone please help me and tell me what is wrong in my approach for the question 431C - k-Tree. I am trying Dynamic Programming.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
const int MOD = 1000000007;
vector<vector<int>> memo;
int dp(int k, int n, int d, int found)
{
if(n==0)
{
if(found) return 1;
else return 0;
}
if(n<0)
{
return 0;
}
if(memo[n][found]!=-1)
{
return memo[n][found];
}
int total = 0;
for(int i=1; i<=k; i++)
{
if(n-i < 0) break;
total = (total%MOD + dp(k, n-i, d, found || i>=d)%MOD)%MOD;
}
return memo[n][found] = total%MOD;
}
int32_t main()
{
int k, n, d;
cin >> k >> n >> d;
memo = vector<vector<int>>(n+1, vector<int>(2, -1));
cout << dp(k, n, d, 0) << "\n";
return 0;
}
Fails on Test case 5: 4 3 2
Expected: 6
Output: 3