In the United States, coins are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of {d1,...,dk} units. We want to count how many distinct ways C(n) there are to make change of n units. For example, in a country whose denominations are {1, 6, 10}, C(5) = 1, C(6) to C(9) = 2, C(10) = 3, and C(12) = 4.
(a) How many ways are there to make change of 20 units from {1, 6, 10}?
(b) Give an efficient algorithm to compute C(n), and analyze its complexity.