Find the minimum number of coins

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

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

StackExchange Code Review Q#92811, answer score: 4