0
$\begingroup$

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)

$\endgroup$
5
  • $\begingroup$ The better one is the one that works. Can you prove that either approach produces the minimal number of coins? For example what happens if you want to return 198 units and the available coins are 100, 99 and 1 unit? On the positive side, both are excellent for learning. $\endgroup$
    – gnasher729
    Dec 12, 2022 at 17:10
  • $\begingroup$ What about a single line of comment above each function that tells the reader what each function is supposed to do? $\endgroup$
    – gnasher729
    Dec 12, 2022 at 17:11
  • $\begingroup$ They both work, on your example, they both return 2 (99+99). They both do the same thing, they compute the minimum number of coins that sum to the total target sum. $\endgroup$
    – JeanMi
    Dec 12, 2022 at 17:16
  • $\begingroup$ I have found two ways [to code something] As in developed both myself, or as in exercising a web search engine? If the former, check out CODE REVIEW@SE's tag comparative-review. $\endgroup$
    – greybeard
    Dec 13, 2022 at 7:37
  • $\begingroup$ both implementations are mine, but this is a very common problem, thus similar implementation are obviously available online $\endgroup$
    – JeanMi
    Dec 13, 2022 at 7:41

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ My usage of variables is mixed up. The order of explanation seems confusing. I will update. $\endgroup$
    – John L.
    Dec 14, 2022 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.