Posts

Showing posts from October, 2015

Memoization

Image
You know when you jot down some phone numbers in the little memo near your phone? Well, not sure how many people still do that, but whenever they do it they are doing what Computer Scientists call Memoization : the process of annotating data in a memo for quick reference in the future. Memoization is the technique primarily used in a field of Algorithms called "Dynamic Programming", commonly known as DP. DP is hard to grasp. At least for me. It is a different paradigm compared to Recursion, and similarly to recursion, you need to solve hundreds of problems before getting any good at DP. I'm not good at DP at all. But I do want to exemplify a simple use of memoization, using a generalization of the second most famous DP problem (the first most famous being Factorial): Fibonacci. As you may recall, Fibonacci is a simple recursive formula that describes the growth in population for a certain species of rats. It is defined as follows: Fib(n) = n (for n<=1) Fib