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;
}
