PythonのMemoizationを使って簡単な「ATM」を計算する

Question

(amount, bills, n)を受け取るコードを作成しました。 billsは使用可能な現金票のタプルであり、nは金額を受け取るために正確に請求書を使用しなければならない回数です。例えば

：

atm_rec（70（5,10）7）真

及び=：

atm_rec（10（2,3,5）6 ）= False

再帰を使用して次のコードを作成しました

def atm_rec(amount, bills, n): 
if amount==0: 
    if n==0: 
     return True 
    else: 
     return False 
elif amount<0: 
    return False 
elif len(bills)==0 and amount!=0: 
    return False 
else: 
    tmp = atm_rec(amount - bills[-1],bills,n-1) 
    tmp2 = atm_rec(amount,bills[0:-1], n) 
    return tmp or tmp2 

は、今私がメモ化を使用して、それをより効率的にしたい（dictのキーはamountとnのタプルであり、値はブールです）何とかコードはずっとlaggierです。何かアドバイスはなぜですか？

def atm_mem(amount, bills, n,memo = None): 
if amount==0: 
    if n==0: 
     return True 
    else: 
     return False 
elif amount<0: 
    return False 
elif len(bills)==0 and amount!=0: 
    return False 
if memo==None: 
    memo={} 
key = (amount, n) 
if memo is not None and key not in memo: 
    tmp = atm_mem(amount - bills[-1], bills, n - 1, memo) 
    tmp2 = atm_mem(amount, bills[0:-1], n, memo) 
    memo[key] = tmp or tmp2 
return memo[key] 

Answer 1

問題は、memoキャッシュを使用していないことです。これは

if memo is not None: 
    tmp = atm_mem(amount - bills[-1],bills,n-1,memo) 
    tmp2 = atm_mem(amount,bills[0:-1], n, memo) 
    memo[(amount,n)]=tmp or tmp2 

は、memoが設定されていても実行されます。

あなたはこのように、memoはあなたのキーが含まれているかどうかをチェックして、計算を避けるためにあります：(amount,n)が既に計算されているとき

key = (amount,n) # compute tuple only once 
if memo is not None and key not in memo: 
    tmp = atm_mem(amount - bills[-1],bills,n-1,memo) 
    tmp2 = atm_mem(amount,bills[0:-1], n, memo) 
    memo[key]=tmp or tmp2 
return memo[key] 

はそう、あなたがifに入力していない、ただ前を発行計算結果。