Solution: Money Change Again

Solution

An optimal way to change $26$ requires seven coins. Let’s consider an arbitrary subset of an optimal solution, e.g., four coins within a rectangle shown below sum up to $15$.

Stop and think: Can we change $15$ cents with three coins?

No, we can’t. If there was a way to change $15$ with three coins, we would replace the highlighted four coins and get a change of $26$ with six coins (rather than seven). This example reveals an important property that many problems solved by the dynamic programming technique share:

Remember: A solution to a problem contains solutions to all its smaller subproblems.

This property allows us to find a solution for a problem by solving smaller subproblems first.

Let $change(money)$ be the minimum number of coins of denominations $1$, $3$, and $4$ needed to change $money$ and $(c_1,...,c_k)$ be an optimal change for $money$ so that

$$c_1+\ldots+c_k =money.$$

Then,

$$c_1+\ldots+c_k−1 =money−c_k.$$ ...