3. (30 pts) The cashier's (greedy) algorithm for making change doesn't handle arbitrary denominations optimally. In this problem you'll develop a dynamic programming solu tion which does, but with a slight twist. Suppose we have at our disposal an arbitrary number of cursed coins of each denomination d, d2,... ,dk, with d > d2 > > dk, and we need to provide n cents in change. We will always have dk - 1, so that we are assured we can make change for any value of n. The curse on the coins is that in any one exchange between people, with the exception of i -k- 1, if coins of denominatiorn d, are used, then coins of denomination di+1 cannot be used. Our goal is to make change using the minimal number of these cursed coins (in a single exchange, i.e., the curse applies) (a) (10 points) For i E {1, k), n E N. and b {0.1), let C(i, n, b) denote the number of cursed coins needed to make n cents in change using only the last i denominations dk-i+1, dk-i+2,...,d only if i d2 > > dk, and we need to provide n cents in change. We will always have dk - 1, so that we are assured we can make change for any value of n. The curse on the coins is that in any one exchange between people, with the exception of i -k- 1, if coins of denominatiorn d, are used, then coins of denomination di+1 cannot be used. Our goal is to make change using the minimal number of these cursed coins (in a single exchange, i.e., the curse applies) (a) (10 points) For i E {1, k), n E N. and b {0.1), let C(i, n, b) denote the number of cursed coins needed to make n cents in change using only the last i denominations dk-i+1, dk-i+2,...,d only if i