Memoization By Hand in Python Function Using Tuples as Cache Keys

Question

I'm trying to implement by-hand memoization in the following function, which calculates the optimal please of eating chocolates given that waiting supposedly increases the pleasure:

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)

I want to use a cache dictionary to store prvious results, but I'm stuck on the implementation. Here's my attempt so far:

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)

I'm stuck on what to use as the key/value for storing the left/right results.

Can anyone help me to complete the memoized version of the function please?

Answer 1

Store the result in your cache before you return.

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

There's no need to store the result of the base case.