Python计算需要最少数量

题目：用面额1，2，5面值的钱币，以最少的张数凑齐13元，需要多少张纸币？

思路1：依次计算从1-13张纸币，每种情况下对应的币值都有什么，对于最先满足13结果的数目，就是需要的纸币。

话不多说，看代码：

def check(price, denoms):
    sums = set() 
    for number in range(1, price+1):
        sums = {s+d for s in sums for d in denoms} or set(denoms)
        if price in sums:
            return number
if __name__='__main__':
    print(check(13, [1, 2, 5]))
#结果是：4

思路2：依次计算从1-13元，计算出所有币值需要的最小数量。

看代码：

def check(price, den):
    coins_need = [0 for _ in range(min(den))]
    for money in range(min(den), price+1):
        min_coins = money
        for coin in [d for d in den if d <= money]:
            if coins_need[money-coin]==0 and money not in den:
                min_coins = 0
                break
            else:
                min_coins = min(min_coins, coins_need[money-coin]+1)
        coins_need.append(min_coins)
    return coins_need[-1] if coins_need[-1] else None