Memoize - Leetcode Solution

The Memoize problem on LeetCode involves creating a memoization function that recursively calculates the value of a given function for a given input but also stores the computed value for future use in order to improve performance.

The problem prompts you to implement a memoization function memoize(func: Callable[..., Any]) → Callable[..., Any] that takes as input a function func and returns a memoized version of the function. The memoized version should cache the results of previous calls to the function for the same set of inputs. If the function is called again with the same input, the memoized version should simply return the cached result instead of recomputing it.

To solve this problem, we can create a dictionary to store the computed values of the function for different inputs. We can then modify the original function to first check if the computed value for a given input already exists in the dictionary. If it does, we can simply return that computed value. Otherwise, we can compute the value using the unmodified function and then cache the result in the dictionary for future use.

Here is a detailed solution to the Memoize problem on LeetCode:

from typing import Any, Callable

def memoize(func: Callable[..., Any]) -> Callable[..., Any]:
    cache = {}  # dictionary to store computed values 

    def memoized_func(*args: Any) -> Any:
        if args in cache:  # if input already computed, return cached value
            return cache[args]
        else:
            result = func(*args)  # compute result using original function
            cache[args] = result  # store computed result for future use
            return result

    return memoized_func  # return the memoized function

In this code, we first define the dictionary cache to store the computed values of the original function. We then define a nested function memoized_func that takes any number of arguments (*args) and returns the computed result of the original function for those arguments.

In the body of memoized_func, we first check if the arguments have already been computed by checking if they exist as keys in the cache dictionary. If the arguments exist in the cache, we simply return the previously computed value. If not, we compute the value using the original function func and store the computed value in the cache dictionary with the arguments as keys. Finally, we return the computed value.

Lastly, we return the memoized_func function object as the memoized version of the original function.

To use this memoization function on a specific function, we simply need to call memoize and pass in the function that we want to memoize. Here is an example using the Fibonacci function:

@memoize  # memoize the Fibonacci function
def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 55 (computed)
print(fibonacci(10))  # 55 (cached)

In this code, we first define the Fibonacci function and use the @memoize decorator to memoize the function. We then call the Fibonacci function twice with the same input of 10. The first call will compute the value (55), while the second call will return the cached value (55), since the results for fibonacci(10) were stored in the cache after the first call.

1