在 Python 上使用 Memoization 计算一个简单的 'ATM'

Question

我创建了一个接收 (amount, bills, n) 的代码。 bills 是可用现金账单的元组，n 是您必须准确使用账单才能收到金额的次数。

例如：

atm_rec ( 70 (5,10) 7 )=True

和：

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 的元组，值是布尔值）但不知何故代码更加滞后。有什么建议吗？

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 是否包含您的密钥来避免计算，如下所示：

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]

所以当(amount,n)已经计算出来的时候，你不用再输入if，直接把预计算的结果发出来

在 Python 上使用 Memoization 计算一个简单的 'ATM'

calculating a simple 'ATM' using Memoization on Python

python

recursion

memoization