Finding minimal amount of coins to reach n

Question

According to my syllabus, this is a dynamic programming problem yet the explanation to the problem I’m supplied with is really confusing and not close to being understandable.

The problem is such:

You are required to give change equal to n (n is a positive nonzero integer, not necessarily bigger than biggest coin) with a given set of k different coins such that each coin has a positive nonzero “value”.

The problem is to find the combination with least amount of coins that is equal to n.

The only method of solution I can come up with is the 'brute' approach, so if I have the set {k1,k2,k3} of coins, I'll need to calculate f(n-k1), f(n-k2), f(n-k3) and for each of f(n-k_i) I'll have to calculate another 3 possibilities, which lead to exponential complexity.

However, I've read that this is possible to solve in O(n) time, yet all explanations I've seen were really math-based and non-intuitive.

I’m really eager to understand this solution, so any source of information regarding this problem could assist in many ways.

Thanks!

Answer 1

This problem is similar to the Knapsack problem. The only difference is that in your case you need to minimize (the amount of coins) instead of maximize (the amount of items in the bag).

The problems are very similar, I think you can get the solution alone :)

Answer 2

You are on the right track that, given a change amount $n$ and denominations $k_1, k_2, k_3$, to compute the minimum number of coins $f(n)$ for change amount $n$ you need to compute $f(n-k_1)$, $f(n-k_2)$ and $f(n-k_3)$.

The main objective is to derive a recursive equation for $f(n)$. Imagine you are given the minimum number of coins for change amount $n$, one coin at a time. In the last step, there are three cases for the value of the last coin: the coin had value $k_1$, and that before that step the change amount $n-k_1$ was given to you optimally, i.e. using $f(n-k_1)$ coins, for a total of $f(n-k_1)+1$ coins. Similarly for the other two cases. This gives the recursive equation $f(n) = min\{f(n-k_1), f(n-k_2), f(n-k_3)\}+1$.

Now that we have a recursive equation for $f(n)$, we can implement it using top-down recursion. To compute $f(n)$ in linear time, you can store the values of smaller subproblems $f(n-k)$ for various $k$ in a table $T$ (stored as a dictionary in the pseudocode below) before returning its value, so that each subproblem is solved only once. This method is called top-down recursion with memoization. Here's the pseudocode:

function f(n):
    if n = 0 then return 0
    if n in {k_1, k_2, k_3} then return 1
    if n in T then return T[n] #since subproblem was solved previously, just do a lookup
    else #need to compute and store T[n] before returning a value
        temp = min{f(n-k_1), f(n-k_2), f(n-k_3)} + 1
        T[n] = temp  #memoization: store solution to subproblem before returning solution
        return T[n]