Suppose that the denominations of the coins in a country are $1,5,10MM{d}_{i}M?d_1(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 $d_i$ 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?