python - 如何递归递增列表中的第一个值并附加到 python 中的嵌套列表？

Question

我编写了一个名为 change 的函数，它接受一个 int 和一个硬币列表。

它递归地检查创建该数量所需的最少硬币数量并返回该数字。现在我正在尝试修改此函数以采用相同的输入，但返回一个包含硬币数量的列表和一个已使用硬币的列表。

def change(amount, coins):
    if amount == 0:
        return 0
    if coins == []:
        return float("inf")
    if coins[0] > amount:
        return change(amount, coins[1:])
    use_it = 1+change(amount-coins[0], coins)
    lose_it = change(amount, coins[1:])
    return min(use_it, lose_it)

我开始修改这段代码，但我不确定如何操作返回值，因为它是一个列表:

def giveChange(amount, coins):
    if amount == 0:
        return [0, []]
    if coins == []:
        return [float("inf"), []]
    if coins[0] > amount:
        return giveChange(amount, coins[1:])
    use_it = 1 + giveChange(amount-coins[0], coins)
    lose_it = giveChange(amount, coins[1:])
    listOfCoins = 
    return [min(use_it, lose_it), listOfCoins]

到目前为止我已经有了这个，但是我的 use_it 行是错误的，因为该函数现在返回一个列表。我可以简单地这样做吗:

use_it = 1 + giveChange(amount-coins[0], coins)[0]

我不确定如何建立硬币列表，以便我可以在最后返回硬币数量。

Answer 1

return a list with the number of coins and a list of coins used.

我认为这就是您要找的:

def giveChange(amount, coins):
    if amount == 0:
        return [0, []]
    if coins == []:
        return [float("inf"), []]
    if coins[0] > amount:
        return giveChange(amount, coins[1:])
    [use_it_amt, use_it_list] = giveChange(amount-coins[0], coins)
    [lose_it_amt, lose_it_list] = giveChange(amount, coins[1:])
    if use_it_amt+1 < lose_it_amt:
        use_it_list.append(coins[0])
        return [use_it_amt+1, use_it_list]
    else:
        return [lose_it_amt, lose_it_list]

在这里您可以看到它正在运行:https://repl.it/Bn2T

因为这是动态编程，所以最好使用内存表来防止重新计算子问题，此外它依赖于堆栈，如果递归调用的数量太大，它会给你 StackOverflow。