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, но я не знаю, как его использовать. Может ли кто-нибудь показать мне, как?

EDIT: идея, как использовать 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): 
    ...