Fibonacci Algorithm

Naive Fibonacci Algorithm

 public static long fib(int N) {
     if (N == 0) return 0;
     if (N == 1) return 1;
     return F(N-1) + F(N-2);
 }

Dynamic Programming – Recursion + Memoization

Dynamic Programming – careful brute force, break it into sub problems, solve the sub problems and reuse the solution.  Richard Belman invented Dynamic Programming as a means to explain mathematical research he was conducting.

Naive recursive algorithm as above, exponential time, running time as recurrance:

T(n) = T(n-1) + T(n-2) + O(1)
T(n) >= 2T(n-2) 
  which is of the order of 2 to the power of n/2

Memoized DP algorithm:  if we need to compute fib(n), if n in memo, return memo[n], else compute fib(n) and store it.  memo is initially an empty dictionary.  Then fib(k) only recurses the first time it’s called for all k.  Memoized calls cost constant time.  Number of non-memoized calls is n, non recursive work per call is constant.  Therefore running time is linear  The best algorithm for calculating Fibonacci numbers is time proportional to log(n).

# best time achieved by resolving subproblems in advance
fib = {}
for k in range(1, n+1):
   [ if k<= 2: f=1
   [ else: f=fib[k-1] + fib[k-2]
     fib[k]:f
return fib[n]

import java.util.HashMap;

public class Fibonacci {
  static HashMap<Integer, Long> fibMap = 
                             new HashMap<Integer, Long>();
  
  // for n >= 1
  public static long fib(int n) {
    if (n <= 2) return 1; // quicker than lookup
    // look up in map, returns null if key doesn't exist
    if (fibMap.containsKey(n)) return fibMap.get(n);
    long f = fib(n-1) + fib(n-2);
    // store new fib in map
    fibMap.put(n, f);
    return f;
  }

  public static void main (String[] args) {
    for (int i = 0; i < 92; i ++) {
      System.out.println(i + " : " + fib(i));
    }
  }
}