题目

今有面值为 1、5、11 元的硬币各无限枚。
想要凑出 n 元，问需要的最少硬币数量。
查看详情
话不多说先看代码

代码

coins = [1, 5, 11]
def minCoinRounding(number, coin):
    eachNumber = [float("inf")]*(number - 1)
    coinNumber[0] = 0
    value = 0
    for value in range(1, number - 1):
        for coinValue in coin:
            temp = value - coinValue
            if temp >= 0:
                eachNumber[value] = min(coinNumber[value], coinNumber[value - coinValue] + 1)
    return coinNumber[value]

print(minCoinRounding(300, coins))

解释


通过代码可以看出，通过从1到目标数值不停与硬币的面额相比较从而获取最少的硬币数量。

value coinNumber
1 1
2 2
... ...
4 4
5 1
6 2
7 3
... ...
9 5
10 2
11 1
12 2
... ...