在使用元组作为缓存键的 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)

我不知道用什么作为 key/value 来存储 left/right 结果。

谁能帮我完成功能的备忘版？

Answer 1

在 return 之前将结果存储在缓存中。

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)]

这样可以确保您的缓存

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

Memoization By Hand in Python Function Using Tuples as Cache Keys

python

memoization