Memoization

**Memoization **is a dynamic programming technique in which solutions to subproblems are stored so they can be used in solutions to later problems. As an example, consider the Fibonacci Problem. In the recursive solution to this problem, we have many values of n for which fib(n) is being calculated more than once. Take the pseudocode calculation of fib(5), for example:
1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
As you can see, fib(2) is being calculated four times, when it should only need to be calculated once. In order to avoid this, we instead save the solutions to problems we have already solved. Then, if we need to solve the same problem later, we can retrieve and reuse our already-computed solution. If we are sure we won't need a particular solution anymore, we can throw it away to save space (see Sliding Window Trick. In some cases, we can even compute the solutions to subproblems we know that we'll need in advance.

page revision: 0, last edited: 11 Nov 2007 04:21