Fibonacci Sequence 

We are all familiar with  Fn = F(n-1) + F(n-2)  

Non-Dynamic Way:  Recursion

  public static long fibonacci(long number) {
    if ((number == 0) || (number == 1)) // base cases
      return number;
    else
      // recursion step
      return fibonacci(number - 1) + fibonacci(number - 2);
  }

Above,  is the recursive non-Dynamic Programming way.  As you can see above,  The Function "fibonacci()", is called Twice on the return line .   This ends up being extremely costly as both functions will eventually be calling the same values  multiple times as it goes down in a "tree like fashion" because each time the function is called it splits into 2 peices.  

To show what I mean here -- Take a look a the pictures below for the the calls of  fibonacci(6) .

As you can see each number gets split up -- It becomes costly in memory and time when we get near the bottom.   As in, the higher your Fibonacci Number is, it will take exponentially longer to compute,  

On a recursive Fibonacci(6)

F(5) is seen once.
F(4) is seen 2 times
F(3) is seen 3 Times
F(2) is seen 5 Times
F(1) is seen 8 Times
F(0) is seen 5 Times.   

A total of 18 Repeates for such a low value of N .  The number of repeats grows extremely fast your starting N gets larger. 

Summary:

• Calculating Fibonacci becomes Excessively Slow  if you need to have a large Fibonacci Number.
  • This is because calculating it this way, creates a Tree like structure 
• You are repeating previous calculated values , which is wasteful

Solution - Dynamic Programming 

To eliminate Repeats, which results in a Linear solution  -- we will use Memoization, which in other words means , Store Previous Values in a list, that can be recalled in the Next cycle.

	public static void DynamicFib(int n) {

		// We are creating an Array for Storage/Memoization
		// This will allow us to call previous calculated values without
		// Having to go into a tree-costly spiral
		int[] T = new int[n];
		
		
		// Linearly -- Build the Array with Values
		for (int i=0;i<n;i++) {
                        // Base-Case
			if (i <=1) T[i] = i;
			else {
				// Store value with   T[i-1] (which is calling T's previous value from last cycle)
				T[i] = T[i-1] + T[i-2];
			}
			
		}
		
		// We can print out the sequence if we like since we built hte values
		for (int i=0;i<T.length;i++) {
			System.out.println(i+1 + ": " + T[i]);
		}
	}

So as I stated above, the idea is store values that we've already calculated to be used in the next sequence.

If we ran this program with N = 10  then the array would be filled with the following.

T[0] = 0
T[1] = 1
T[2] = 1
T[3] = 2
T[4] = 3
T[5] = 5
T[6] = 8
T[7] = 13
T[8] = 21
T[9] = 34

 Summary:

• Use Array's to store previous values for the next interation to use
• In order set the value of T[6], we simply add T[5] and T[4] together, which is 5 +3 = 8.
• Since the operation is only calling a previously stored value, the calculation is extremely fast.
• This is a ground-up approach , so you have to start at the T[0] , or the basecase.  This is because higher N values need the previous minimum values when creating the table.