Answer to Question 3-3

Recurrences for C are as follows.

  C(1) = 1
  C(x) =      MIN              (1 + C(n - ci))
         i in {1,...,k}
             ci ≤ x

That is, try using each coin value that does not exceed x. Charge 1 for that coin, and add the number of coins needed to make the amount left over.

A time-efficient algorithm to compute C is as follows. I assume that we can use elementary list comprehensions.

  C(x)
    coins = an array of x integers, indexed 1,...,x
    coins[1] = 1
    for j = 2,...,x
      coins[j] = 1 + min [coins[j - ci] | i in {1,...,k}, ci ≤ j]
    end for
    return coins[x]