Help me understand this dp problem !

I am new to dynamic programming. I can’t figure out how the solution given to this problem works, please explain how the answer given works. I’d also appreciate links to various resources to learn dp, thanks
The question statement :- Suppose there are several denominations of
coins in a currency and you are trying to make a particular amount N. Assuming that you have an
infinite number of coins of each denomination, what is the minimum number of coins you need?

Answer statement :- The state is simply the
amount that we are trying to make - we’ll represent the state of trying to make the change for n by the
integer n.

The recurrence relation then follows:
f(n) = 1 + min denominations d (f(n - d))

int memo[128]; // initialized to -1
int min_coin(int n) {
// base cases
if ( n < 0) return INF ;
if ( n == 0) return 0 ;
if (memo[ n ] != -1)
/ / recurrence relation

int ans = INF;
for (int i=0; i<num_denomination; i++)
{ ans = min(ans, min_coin(n - denominations[i]));}

return memo[n] = ans+1;
}

http://people.csail.mit.edu/bdean/6.046/dp/

1 Like

See the MakingChange Problem.See others as well.There are what u might say a classic DP bunch.

thanks for the link :slight_smile:

It looks as if a simple knapsack problem… but as I m not clear with your description… please provide a link to the problem…

//