Suppose that the denominations of the coins in a country are d1 < d2 < < dn (e.g., 1, 5, 10, 25 for the United States). The problem to consider is:

Given an integer M, what is the minimum number of coins needed to make M cents in change

(a) Under what condition(s) on the denominations di are you able to make change for any amount M?

(b) Give a dynamic programming algorithm to solve the problem.

(c) How fast is your algorithm?