Changing Money Using Dynamic Programming

To avoid the many recursive calls that are needed to compute MinNumCoins(money), we’ll use a dynamic programming strategy. Wouldn’t it be nice to know all the values of MinNumCoins(money − coin$_{i}$) by the time we compute MinNumCoins(money)? Instead of the time-consuming calls to RecursiveChange(money − coin$_{i}$, Coins), we could simply look up the values of MinNumCoins(money − coin$_{i}$) in an array and thus compute MinNumCoins(money) using just |Coins| comparisons.

The key to dynamic programming is to take a step that may seem counterintuitive. Instead of computing MinNumCoins(m) for every value of m from 76 downward toward m = 1 via recursive calls, we’ll invert our thinking and compute MinNumCoins(m) from m = 1 upward toward 76, storing all these values in an array so that we only need to compute MinNumCoins(m) once for each value of m. MinNumCoins(m) is still computed via the same recurrence relation:

$$\begin{aligned} \operatorname{MinNumCoins}(m)=\min \left\{\begin{array}{l}\operatorname{MINNUMCOINS}(m-5)+1 \\ \operatorname{MINNUMCOINS}(m-4)+1 \\ \operatorname{MINNUMCOINS}(m-1)+1\end{array}\right. \end{aligned}$$

For example, assuming that we’ve already computed MinNumCoins(m) for $m < 6$,

$$\begin{aligned} \operatorname{MinNumCoins}(6) & =\min \left\{\begin{array}{l}\text { MINNUMCOINS }(1)+1=2 \\ \text { MINNUMCOINS(2)+1 }=3 \\ \text { MINNUMCOINS }(5)+1=2\end{array}\right. \\ & =2 .\end{aligned}$$

Following the same reasoning,

$$\begin{aligned} \operatorname{MinNumCoins}(7) & =\min \left\{\begin{array}{l}\operatorname{MINNUMCOINS}(2)+1=3 \\ \operatorname{MINNUMCOINS}(3)+1=4 \\ \operatorname{MINNUMCOINS}(6)+1=3\end{array}\right. \\ & =3 .\end{aligned}$$

Continuing these calculations results in the figure below.