Memoization
Memoization 1. What Is Memoization? Memoization: a way of implementing a search that records information about states it has already visited, so that the same state is never traversed (recomputed) more than once. Memoization = DFS + an extra dictionary (cache) If the state has been searched before: look it up in the dictionary and return the stored result directly. If the state has not been searched before: keep searching, and finally record that state’s result into the dictionary. 2. Worked Example — Fibonacci Sequence Problem Define the Fibonacci sequence as:
Read note →