Find the minimum number of coins

Question

I'm trying to learn dynamic programming and the most popular one is to find the minimum number of coins for the change. I come up with this but I just want to improve this code which I think it could be shorter in Python but I'm new to Python too.

import sys
coins = [1, 3, 5]
min_coin = [sys.maxint] * 20
min_coin[0] = 0
for min_of_i in range(20):
 for c in coins:
 if c <= min_of_i and (min_coin[min_of_i - c] + 1 < min_coin[min_of_i]):
 min_coin[min_of_i] = min_coin[min_of_i - c] + 1
print min_coin

Answer 1

This is already pretty short. Making it shorter doesn't seem a good objective, and risks hurting readability. That being said, there are a few things you could do.

You could do this in one step:

min_coin = [sys.maxint] * 20
min_coin[0] = 0

Like this:

min_coin = [0] + [sys.maxint] * 19

While at it, why are there 20 elements? Your program will find the minimum number of coins up to 19, and I have a feeling that you actually want it for 20. In which case you would need:

min_coin = [0] + [sys.maxint] * 20

And then use range(21) in the loop. However, you shouldn't hard code this number, give it a name, like target_amount, and use that.

Speaking of names, many of the names in your code can be better:

• min_coin is a list, so plural min_coins would be better
• min_of_i is actually an amount

One more optimization is possible by flipping the order of the nested loops. In the current code you need an if statement to skip the amounts that are too small for the coin. If you make the loop over coins to be the outer loop, then you can set a starting value for the inner value to make the if statement unnecessary.

def get_min_coins(coins, target_amount):
 n = len(coins)
 min_coins = [0] + [sys.maxint] * target_amount
 for i in range(1, n + 1):
 for j in range(coins[i - 1], target_amount + 1):
 min_coins[j] = min(min_coins[j - coins[i - 1]] + 1, min_coins[j])
 return min_coins

Answer 2

To be honest, I don't understand what your program does, even the hints that it has something to do with coins and change don't help me.

So, one major step to improve the code would be to add some documentation:

• What does the program do?
• What is its input and in what form do I have to give it to the program?
• What is its output and how is it formatted?

Answer 3

I find your naming to be baffling, in particular min_of_i. Here is the same program with some variables renamed.

import sys
denominations = [1, 3, 5]
coins_needed = [sys.maxint] * 20
coins_needed[0] = 0
for amt in range(20):
 for coin in denominations:
 if coin <= amt and coins_needed[amt - coin] + 1 < coins_needed[amt]:
 coins_needed[amt] = coins_needed[amt - coin] + 1
print coins_needed

However, it is inelegant to have to use sys.maxint and to write coins_needed[amt - coin] + 1 twice. You can solve both problems by using min() with a generator expression.

denominations = [1, 3, 5]
coins_needed = [0] * 20
for amt in range(1, len(coins_needed)):
 coins_needed[amt] = min(
 1 + coins_needed[amt - coin] for coin in denominations if coin <= amt
 )
print(coins_needed)

Alternatively, you can just grow the results incrementally.

denominations = [1, 3, 5]
coins_needed = [0]
for amt in range(1, 20):
 coins_needed.append(min(
 1 + coins_needed[amt - coin] for coin in denominations if coin <= amt
 ))
print(coins_needed)

I've also added parentheses after print to make it compatible with Python 3.

Answer 4

First of all, that's not dynamic programming as I understand the term. You haven't broken the problem down into simpler sub-problems, and in fact you have used an algorithm so convoluted in its logic that it's inordinately difficult to understand.

Divide the problem into two parts: (1) a function to compute the number of coins needed to achieve a given total. Here it is:

coins = (5,3,1) # order this list max to min
def coin_count(x):
 n = 0
 for a_coin in coins:
 count = x // a_coin
 n += count
 x -= a_coin * count
 return n

(2) You simply call this function to generate any desired output. You want the answers for the first 20 integers, so...

min_coin = [coin_count(n) for n in range(20)]
print min_coin

Which gives the same answer as yours, except it only declares one variable (coins), creates a re-usable function (coin_count) and can easily be modified for different coin denominations and different output requirements. I can only guess whether that qualifies as dynamic programming, but I think it's a far better approach.

• Gareth Rees: This gives the wrong answer for coins = (3,2) and x=4.
• 200_success: The greedy algorithm that you have implemented works for most sets of denominations in common usage, but not in the general case.