What is the best way to solve the coin change problem using dynamic programming?

Question

I have found two ways of applying dynamic programming to the coin change problem of finding the minimum number of coins from a given set of denominations to make a given sum. I wanted to know if one is better than the other:

def money_dyn1(m, coins):
    a = [[float("+inf") for j in range(m + 1)] for i in range(len(coins) + 1)]
    for i in range(len(a)):
        a[i][0] = 0

    for i in range(1, len(a)):
        for j in range(1, len(a[0])):
            if coins[i - 1] > j:  # if the coin is bigger than the sum to reach
                a[i][j] = a[i - 1][j]
            else:
                a[i][j] = min(a[i - 1][j], a[i][j - coins[i - 1]] + 1)

    print(a[-1][m])

and

def money_dyn2(m, coins):
    a = [None for j in range(m + 1)]
    a[0] = 0

    for i in range(0, len(a)):
        for c in coins:
            if i + c < len(a) and a[i] != None:
                if a[i + c] == None or a[i + c] > a[i]:
                    a[i + c] = a[i] + 1
    return a[m]

I find the later much simpler to understand, but when I lookup examples on the internet about DP applied to this problem, it seems that most of the solutions implement the first implementation (using the 2D array).

Is one of those implementation better than the other ? What are the differences between those ? (both mathematically and algorithmically)

Answer 1

Nice question!

We are computing entries in a matrix.

We are computing the minimum number $a[i][m]$ of coins to yield value $m$ using the first $i$ coins for all valid $i$'s and $m$'s using the recurrence relation $$a[i][m]=\begin{cases}a[i-1][m]&\text{if }m<coins[i]\\\min(a[i-1][m], a[i-1][m-coins[i]+1)&\text{otherwise}\end{cases}$$ starting from the initial numbers for $i=0$ or $m=0$.

Two ways to computing them: by rows and by columns

All $a[i][m]$'s form a two-dimensional matrix, with each row corresponding to fixed set of available coins and each column corresponding to a fixed amount of money. As you noted, there are two routes to compute all entries of that matrix.

• Row by row starting from the row of no coins. This is money_dyn1.
• Column by column starting from the column of zero money. This money_dyn2.

There are not much difference between the two ways

If the route by rows as implemented by money_dyn1 is more popular, I would assume that is because the immediate reaction of people is more like "if I have this set of coins, how do I select/adjust coins to give various amount of change?" instead of "if the amount of change is this, how do I select/adjust coins for my various coin sets?" The amount of change to give to others is naturally the changing part of a setup while the coins I have sounds like real estate that changes infrequently. OK, I am analyzing psychology and social practices, which is somewhat beyond the realm of computer science.

The point is there is not much difference between the two ways, both mathematically and algorithmically.

For example, here is an implementation of the first way, money-dyn1 using 1D-array just as money-dyn2.

def money_dyn1_Apass(m, coins):
    """ A version of money_dyn1 using 1D array"""
    a = [None for _ in range(m + 1)]
    a[0] = 0

    for c in coins:
        for i in range(m - c + 1):
            if a[i] is not None and (a[i + c] is None or a[i + c] > a[i] + 1):
                a[i + c] = a[i] + 1

    return a[m]

Personally, I find both approaches are natural and easy to understand. Most of times, I would assume my students are more comfortable with the first method, but not by a large margin.