Memoization

Lesson 4 of 15 in Coddy's Dynamic Programming 101 course.

Memoization is an optimization technique used in dynamic programming to speed up the programs by caching the results of expensive function calls and returning the cached result when the same inputs occur again.

To implement memoization, you can create a dictionary to store the already computed results, where the keys are the input arguments and the values are the corresponding output results. Before computing the result of a function, you can first check whether the input has already been computed and stored in the dictionary. If so, you can return the cached result instead of computing it again. Otherwise, you compute the result and store it in the dictionary.

list also can be used to implement memoization.

Memoization can significantly speed up dynamic programming algorithms, especially when there are many overlapping subproblems.

Challenge

Easy

Write a Python function called fib that calculates the nth Fibonacci number using memoization.

Use the memo dictionary to store the already computed Fibonacci numbers.
Before computing the nth Fibonacci number, check whether it has already been computed and stored in the memo.
If it has, return the cached result. Otherwise, compute the nth Fibonacci number using the recurrence relation fib(n) = fib(n-1) + fib(n-2), and store the result in the dictionary for future use.