431C. k - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 431C. k

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define m 1000000007
 
int n,k,d;
 
ll dp[2][200];
 
ll func(bool taken, int s)
{
    if(!taken && n-s < d)
        return 0;
  if(s>=n)
  {
    if(s>n)
      return 0;
    if(s==n && taken)
      return 1;
    return 0;
  }
  ll sum=0;
  for(int i=1;i<=k;i++)
  {
    if(i<d)
    {
        if(dp[taken][s+i]==-1)
          sum=(sum+func(taken,s+i)%m)%m;
      else   
          sum=(sum+dp[taken][s+i])%m;
    } 
    else
    {
      if(dp[1][s+i]==-1)
          sum=(sum+func(1,s+i)%m)%m;
      else   
          sum=(sum+dp[1][s+i])%m;
    }
  }
 
  return dp[taken][s]=sum;
 
}
 
int main()
{
    for(int i=0;i<200;i++)
        dp[0][i]=dp[1][i]=-1;
  cin>>n>>k>>d;
  cout<<func(0,0);
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.