Python -更改为Memoization

Question

我已经编写了一个函数，当顺序发生变化时，使用给定的硬币查找n的所有变化。

def find_change(n, coins):
    if n < 0:
        return []

    if n == 0:
        return [[]]

    all_changes = []

    for last_used_coin in coins:
        curr_changes = find_change(n - last_used_coin, coins)

        for change in curr_changes:
            change.append(last_used_coin)

        all_changes.extend(curr_changes)

    return all_changes

print find_change(4, [1,2,3])

上面的代码是“正常的”，现在我想重新编写一次，但作为一个备忘录。将保存在备忘录中的值是可变的，因此我应该使用deepcopy，但我不知道如何使用它。有人能教我怎么做吗？

编辑:如何使用深度拷贝的想法：

from copy import deepcopy
lst1 =[[1], [2]]
lst 2 = deepcopy(lst1)
print lst

然后我们得到：

[[1], [2], [3]]

Answer 1

您唯一可更改的参数是n，因此只需将其用作查找表的键：

if n not in cache:
    ...

你甚至可以把它变成一个装饰器：

def memoized(function):
    cache = {}

    def inner(n, coins):
        if n not in cache:
            cache[n] = function(n, coins)

        return cache[n]

    return inner

@memoized
def find_change(n, coins):
    ...