Changing Money Recursively

Since the greedy solution used by Roman cashiers to solve the Change Problem is incorrect, we’ll consider a different approach. Suppose you need to change 76 denarii, and you only have coins of the three smallest denominations: Coins = (5, 4, 1). A minimal collection of coins totaling 76 denarii must be one of the following:

• a minimal collection of coins totaling 75 denarii, plus one 1-denarius coin;

• a minimal collection of coins totaling 72 denarii, plus one 4-denarius coin;

• a minimal collection of coins totaling 71 denarii, plus one 5-denarius coin.

Recurrence relation

For the general denominations Coins = (coin$_{1}$, … , coin$_{d}$), MinNumCoins(money) is equal to the minimum of d numbers:

$$Mi$$ ...