最小硬币数

davidmou

def money(ownmoney, moneylist,knownlist):
    if ownmoney in moneylist:
        knownlist[ownmoney] = 1
        return 1
    #如果ownmoney 已经在列表中存在其最小硬币数，如3，我就不用再递归啦，直接调用器最小硬币数，也是结束递归的条件
    elif knownlist[ownmoney] >0:
        return knownlist[ownmoney]

    else:
        for each in [c for c in moneylist if c <= ownmoney]:

            numbercoin = 1 + money(ownmoney - each, moneylist,knownlist)
            if knownlist[ownmoney] == 0:
                knownlist[ownmoney] = numbercoin


    return numbercoin


print(money(40,[1,5,10,25],[0]*63))

执行后为什么输出结果是7，40 = 25 + 10 + 5，40的最小硬币数是3，输出结果应该是3才对

isdkz

问题出在第一个if语句中。在该语句中，如果ownmoney在moneylist中存在，那么knownlist[ownmoney]被设置为1，然后返回1。这是正确的。但是在返回之后，递归调用money函数的结果被忽略了，而是直接返回了1。

解决这个问题的方法是，将递归调用的结果存储在一个变量中，并在返回结果之前使用该变量。这样，就可以正确地计算并返回最小硬币数。

以下是修改后的代码：

def money(ownmoney, moneylist, knownlist):
    if ownmoney in moneylist:
        knownlist[ownmoney] = 1
        return 1
    elif knownlist[ownmoney] > 0:
        return knownlist[ownmoney]
    else:
        min_coins = float('inf')  # 初始化最小硬币数为正无穷
        for each in [c for c in moneylist if c <= ownmoney]:
            numbercoin = 1 + money(ownmoney - each, moneylist, knownlist)
            if numbercoin < min_coins:
                min_coins = numbercoin
        knownlist[ownmoney] = min_coins  # 将最小硬币数存储在knownlist中
        return min_coins

print(money(40, [1, 5, 10, 25], [0] * 41))

现在，输出结果将是3，因为40的最小硬币数是3。