User:Gkhan/Fibonacci using memoization and DP

Fibonacci-function using memoization and DP

So how would a fibonacci program using memoization work? Consider the following program (f[n] contains the nth Fibonacci-number if has been calculated, -1 otherwise):

function fib(n)
  if f[n] != -1  
    return f[n]
  else if n == 0 or n == 1
    return n
  else
    f[n] = fib(n-1) + fib(n-2)
    return f[n]
  fi
end function

The code should be pretty obvoius. If the value of fib(n) already has been calculated it's stored in f[n] and then returned instead of calculating it again. That means all the copies of the sub-call trees are removed from the calculation.

The values in the blue boxes are values that already have been calculated and the calls can thus be skipped. It is thus alot faster than the straight-forward recursive algorithm. Since every value less than n is calculated once, and only once, the first time you execute it, the asymptotic running time is$O(n)$. Any other calls to it will take $O(1)$ since the values have been precalculated (assuming the rest of the calls is less than n).

The algorithm does consume alot of memory. When we calculate fib(n), the values fib(0) to fib(n) are stored in main memory. Can this be improved? Yes it can, although the $O(n)$ running time of subsequent calls are obvoisly lost (since the values aren't stored). Since the value of fib(n) only depends on fib(n-1) and fib(n-2) we can discard the other values by going bottom-up. If we want to calculate fib(n), we first calculate fib(2) (fib(0) + fib(1)) then we can calculate fib(3) by adding fib(1) and fib(2). Then we can discard fib(1) and fib(2) since we don't need them to calculate any more values. From fib(2) and fib(3) we calculate fib(4) and discard fib(2), then we calculate fib(5) and discard fib(3), etc etc. The code goes something like this:

function fib(n)
  int u = 0
  int v = 1
  int t;

  for i = 2 to n
    t = u + v
    u = v
    v = t
  repeat
  
  return v
end function

We can, obvouisly, modify the code to store the values in an array for subsequent calls, the point is that we don't have to. This method is typical for dynamic programming. First we identify what subproblems need to be solved in order to solve the entire problem, and then we calculate the values bottom-up using an iterative process.