This content is archived!For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.
Memoization is the act of storing previous answers so they don’t have to be calculated again.
An example of when memoization can be used is with the recursive Fibonacci function.
The following is the unoptimized Fibonacci function.
fib(5) will calculate
fib(4) will also calculate
fib(3), which has already been calculated.
To optimize the function, a global array
cache is initialized with the maximum value of
n of and filled with
-1. The function will then be as follows:
Base cases may be hardcoded into the cache array or in the function.
P1 - HSIUNG