File Name Change, coin_change.py

[Denimbeard]

Request to change coin_change.py to min_coin.py, to better reflect the operation being performed.

"The Minimum Coin Change (or Min-Coin Change) is the problem of using the minimum number of coins to make change for a particular amount of cents."

Versus the current name:
"The Coin Change problem is the problem of finding the number of ways of making changes for a particular amount of cents, using a given set of denominations. It is a general case of Integer Partition, and can be solved with dynamic programming."

Basic:

def count( n, m ):
    if n < 0 or m <= 0: #m < 0 for zero indexed programming languages
        return 0
    if n == 0: # needs be checked after n & m, as if n = 0 and m < 0 then it would return 1, which should not be the case.
        return 1
    return count( n, m - 1 ) + count( n - S[m-1], m )

Dynamic:

func count( n, m )

  for i from 0 to  n+1
    for j from 0 to m
      if i equals 0
         table[i, j] = 1          
      else if j equals 0
         if i%S[j] equals 0
               table[i, j] = 1  
         else 
               table[i, j] = 0;
      else if S[j] greater than i
         table[i, j] = table[i, j - 1]
      else 
         table[i, j] = table[i - S[j], j] + table[i, j-1]

  return table[n, m-1]

Currently, coin_change.py uses this:

def dp_count(S, n):
    if n < 0:
        return 0
    table = [0] * (n + 1)
    table[0] = 1
    for coin_val in S:
        for j in range(coin_val, n + 1):
            table[j] += table[j - coin_val]
    return table[n]

if __name__ == "__main__":
    import doctest

    doctest.testmod()

While the two are related, this does allow for better options to show different versions, even non-optimal ones, for solving problems.

[dhruvmanila]

Hey, thanks for pointing this out. If possible, you can open a PR for this change. I would suggest changing the name to the descriptive version: minimum_coin_change.py or min_coin_change.py

[Denimbeard]

#4108