Making Change

Imagine you live in a country where the coin denominations are $1$ cent, $4$ cents, and $5$ cents.

Consider the problem where you are given some value $n$ and you want to make change for

this value, using the smallest number of coins.

Part $1$: Show that the greedy algorithm $($use the largest value coins first$)$ for making change

fails for these denominations

Part $2$: Describe a dynamic programming algorithm for finding the smallest number of coins

needed in this country to make change for any value of $n.$ Analyze your algorithm.