Dynamic Programming

Dynamic Programming Solution to the
Coin Changing Problem
(1) Characterize the Structure of an Optimal Solution. The Coin Changing problem exhibits opti-
mal substructure in the following manner. Consider any optimal solution to making change for n cents using
coins of denominations d1 , d2 , . . . , dk . Now consider breaking that solution into two different pieces along
any coin boundary.Suppose that the “left-half” of the solution amounts to b cents and the “right-half” of
the solution amounts to n − b cents, as shown below.
b
d1
d3
n−b
d1
d2
d4
d5
d2
Claim 1 The left-half of the solution must be an optimal way to make change for b cents using coins of
denominations d1 , d2 , . . . , dk , and the right-half of the solution must be an optimal way to make change for
n− b cents using coins of denominations d1 , d2 , . . . , dk .
Proof: By contradiction, suppose that there was a better solution to making change for b cents than the
“left-half” of the optimal solution shown. Then the left-half of the optimal solution could be replaced with
this better solution, yielding a valid solution to making change for n cents with fewer coins than the solution
beingconsidered. But this contradicts the supposed optimality of the given solution, →←. An identical
argument applies to the “right-half” of the solution.
2
Thus, the optimal solution to the coin changing problem is composed of optimal solutions to smaller
subproblems.
(2) Recursively Define the Value of the Optimal Solution. First, we define in English the quantity
we shall later define recursively.Let C[p] be the minimum number of coins of denominations d1 , d2 , . . . , dk
needed to make change for p cents. In the optimal solution to making change for p cents, there must exist
some first coin di , where di ≤ p. Furthermore, the remaining coins in the optimal solution must themselves
be the optimal solution to making change for p − di cents, since coin changing exhibits optimalsubstructure
as proven above. Thus, if di is the first coin in the optimal solution to making change for p cents, then
C[p] = 1 + C[p − di ]; i.e., one di coin plus C[p − di ] coins to optimally make change for p − di cents. We don’t
know which coin di is the first coin in the optimal solution to making change for p cents; however, we may
check all k such possibilities (subject to the constraint thatdi ≤ p), and the value of the optimal solution
must correspond to the minimum value of 1 + C[p − di ], by definition. Furthermore, when making change
for 0 cents, the value of the optimal solution is clearly 0 coins. We thus have the following recurrence.
Claim 2 C[p] =
0
mini:di ≤p {1 + C[p − di ]}
if p = 0
if p > 0
Proof: The correctness of this recursive definition is embodied in theparagraph which precedes it.
1
2
(3) Compute the Value of the Optimal Solution Bottom-up. Consider the following piece of pseu-
docode, where d is the array of denomination values, k is the number of denominations, and n is the amount
for which change is to be made.
Change(d, k, n)
1 C[0] ← 0
2 for p ← 1 to n
3
min ← ∞
4
for i ← 1 to k
5
if d[i] ≤ p then
6
if 1 + C[p − d[i]] < minthen
7
min ← 1 + C[p − d[i]]
8
coin ← i
9
C[p] ← min
10
S[p] ← coin
11 return C and S
Claim 3 When the above procedure terminates, for all 0 ≤ p ≤ n, C[p] will contain the correct minimum
number of coins needed to make change for p cents, and S[p] will contain (the index of ) the first coin in an
optimal solution to making change for p cents.
Proof: The correctness of the aboveprocedure is based on the fact that it correctly implements the recursive
definition given above. The base case is properly handled in Line 1, and the recursive case is properly handled
in Lines 2 to 10, as shown below. Note that since the loop defined in Line 2 goes from 1 to n and since
di ≥ 1 for all i, no array element C[·] is accessed in either Line 6 or 7 before it has been computed. Lines 3...