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]