python - 分而治之 - 最小硬币 - 将硬币作为数组返回

Question

下面是最小硬币找零问题的暴力解决方案。它需要一个 int 零钱，这是需要做的零钱，以及一系列硬币面额。它返回进行更改所需的最少硬币。

我如何修改它以返回一个硬币数组？

例如，如果要求找零 10 美分，值为 [1, 2, 5]，它应该至少返回 2 个硬币和一个数组 [0, 0, 2] 来表示两个镍币。

def recMC(coinValueList,change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList,change-i)
        if numCoins < minCoins:
            minCoins = numCoins
     return minCoins

print(recMC([1,5,10,25],63))

Answer 1

与任何递归函数一样，您从保护条件开始 - 告诉您何时完成的测试:

if change in coinValueList:
    return 1

要将其转换为硬币列表，只需返回由 1 个硬币组成的列表:

if change in coinValueList:
    return [ change ]   

在函数的另一部分，您知道递归调用将返回一个列表。因此，只需获取列表并使其成为一个更大的列表:

        numCoins = 1 + recMC(coinValueList,change-i)

变成:

        coins = [ i ] + recMC(coinValueList, change - i)

您还必须更新其他测试。