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;

}