### icode_8990's blog

By icode_8990, history, 9 months ago, ,

So in this problem i am trying to solve it using dynamic programming approach. But I am unable to understand the solution since its written in poor english. I am referring to this tutorial. How is the dp[][] being developed?. it will be great if someone could explain in details since i am a newbie. Thank you in advance!

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int mod = 1e9 + 7;

int dp[100][2];

void add(int &a, int b)
{
a += b;
if(a >= mod)
a -= mod;
}

int main(int argc, char ** argv)
{
int n, k, d;
cin >> n >> k >> d;
dp[0][0] = 1;
dp[0][1] = 0;

for(int i = 1 ; i <= n ; ++i)
{
dp[i][0] = dp[i][1] = 0;

for(int j = 1 ; j <= k ; ++j)
{
if(i-j < 0) break;

if(j < d)
{
}
else
{
}
}
}
cout << dp[n][1] << "\n";
return 0;
}


• -4

 » 9 months ago, # |   0 Auto comment: topic has been updated by icode_8990 (previous revision, new revision, compare).
 » 9 months ago, # |   0 Consider this: dp[sum to be made][do we have an edge with weight at least d]. So now you want to calculate dp[sum][false] and it will be something like this: for (int i = 1; i <= k; i++) dp[sum][false] += dp[sum-i][i >= d]; and dp[sum][true]: for (int i = 1; i <= k; i++) dp[sum][true] += dp[sum-i][true];
 » 9 months ago, # |   +1 try to solve with top — down approach . suppose we are at node x , from node x we can go to each of the k nodes just below it...let our total sum till x node is sum now from node x , we iterate for each possible k values and each time our sum is increased by sum+i;we also use chk variable to check whether we visited an edge with weight >=d for more clearity check my sol . Link
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Thank you so much... it really helped
•  » » » 2 days ago, # ^ | ← Rev. 2 →   +3 how it helped. how u came across this blog. who r u? LOL.why u didn't submitted the solution to this problem?
 » 2 days ago, # |   0 since i am a newbieNo you are unrated
•  » » 2 days ago, # ^ |   0
•  » » » 2 days ago, # ^ |   0 Are you too blind. I am pupil
•  » » » » 2 days ago, # ^ |   0 hi nik7, no i am not blindcan you stop create comment and blog
•  » » » » » 2 days ago, # ^ |   0 *creating