在 Python 函数中使用元组作为缓存键手动记忆

Question

我正在尝试在以下函数中实现手记忆，该函数计算吃巧克力的最佳乐趣，因为等待据说会增加乐趣：

def joy(chocs, day):
n = len(chocs)
if n == 1:
return day * chocs[0]
left = day * chocs[0] + joy(chocs[1:], day + 1)
right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
return max(left, right)

我想使用cache字典来存储以前的结果，但我坚持在实现上。这是我到目前为止的尝试：

def joy(chocs, day, cache={}):
if (chocs, day) in cache:
return cache[(chocs, day)]
n = len(chocs)
if n == 1:
return day * chocs[0]
left = day * chocs[0] + joy(chocs[1:], day + 1)
right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
return max(left, right)

我纠结于使用什么作为存储左/右结果的键/值。

谁能帮我完成函数的记忆版本？

Answer 1

在返回之前将结果存储在缓存中。

result = max(left, right)
cache[(chocs, day)] = result
return result

无需存储基本情况的结果。

Answer 2

只是颠倒你的逻辑

def joy(chocs, day, cache={}):
if (chocs, day) not in cache:
n = len(chocs)
if n == 1:
cache[(chocs,day)] = day * chocs[0]
else:
left = day * chocs[0] + joy(chocs[1:], day + 1)
right = day * chocs[n - 1] + joy(chocs[:n - 1], day + 1)
cache[(chocs,day)] = max(left, right)
return cache[(chocs, day)]

这样就可以确保您的缓存