Memoize function

Another way to perform dynamic programming style is to use memoize function.  The memoize function is a function that can "remember" its past computation so that it will reuse the result instead of recompute.  Using memoize function makes writing a dynamic programming style easier because the code can follow the recurive definition almost literally, hence make it easy to understand and make its correctness obvious.  Because memoize function never repeats the computation that its has already done, it is very fast.

I will demonstrate a memoize function style in implementing a Fibonacci number function.

Definition

Recursive function   (in Python)

def fib(n):
    if( n == 0 ): return 0
    if( n == 1 ): return 1
    return fib(n-1) + fib(n-2)   #  recursive call

When call fib(10), it takes 88 calls to fib().  There are a lot of "repeat" computation.

Here is a memoize version

memo = [0] * 20   # create array size 20, all zero

def fibm(n):
    if( n == 0 ):
        memo[0] = 0
        return 0
    if( n == 1 ):
        memo[1] = 1
        return 1
    if( memo[n] != 0 ):
        return memo[n]
    memo[n] = fibm(n-1) + fibm(n-2)   # recursive call
    return memo[n]

When call fibm(10), it takes only 9 calls to fibm().  No duplicate computation! 

If you observe the sequence of call to fib() and fibm(), you can see that they are different.  This is another important aspect of memoize function style versus the "scanning the table" style of dynamic programming.  To use the scanning table style, you must determine the right sequence first, and then implement for-loop according to that. So, the call sequence occurs according to your plan and not according to the recursive definition.  For memoize function style, the call sequence occurs according to the recursive definition.

Here is the code  and the output.  Please experiment with it.

Hope you enjoy it.