python - 在 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 的元组，值是 bool 值)但不知何故代码更滞后.有什么建议吗？

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 来避免计算，如下所示:

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，只是发出预计算的结果。