Fibonacci Problem Dynamic Programming — Tabulation

To learn about the recursive solution of the same problem : check here fibonacci-problem using recursion

To solve any problem using tabulation you need to populate a table with all possible combinations and derive generic formula.

Let us consider an example — fib(6) can be represented as a table shown below. Let us see how this table can populated based on basic rules of fibonacci.

1. To start with an array will be created with n+1 value of size where n is the input/the fibonacci number to be calculated for. For e.g since we are checking for fib(6), the array can be created for 6 elements.
2. Fill all the array values with 0.

All values are populated with 0 values

3. Update the table with base value. f(0) = 0 and f(1) = 1;

Updating base value to 1

Now applying the rules of fibonacci series.

At any point in the array, ith element will be used to calculate (i+1)th element and (i+2)th element. Applying this rule to each of the elements in the array.

For i = 0,
array[1] = array[1]+array[0] ===> 1 + 0 = 1 
array[2] = array[2]+array[0] ===> 0 + 0 = 0

Array for i = 0

For i = 1
array[2] = array[2]+array[1] ===> 0 + 1 = 1
array[3] = array[3]+array[1] ===> 0 + 1 = 1

Array for i = 1

For i = 2,
array[3] = array[3]+array[2] ===> 1 + 1 = 2
array[4] = array[4]+array[2] ===> 0 + 1 = 1 

Array for i = 2

For i = 3
array[4] = array[4]+array[3] ===> 1 + 2 = 3
array[5] = array[5]+array[3] ===> 0 + 2 = 2

Array for i = 3

For i = 4
array[5] = array[5]+array[4] ===> 2 + 3 = 5
array[6] = array[6]+array[4] ===> 0 + 3 = 3

Array for i = 4

For i = 5
array[6] = array[6]+array[5] ===> 3 + 5 = 8

Array for i = 5

The fib(6) is 6th element in the above array, so fib(6) = 8

So you can derive the formula as

array[i+1] += array[i];
array[i+2] += array[i];

Java Program

public class Solution {
   public static void main(String[] args) {
     // Calling Fib Function for different values : 3,4,40,45
     int[] input = {3, 4, 40, 45};
     for (int num : input) {
        Instant start = Instant.now();
        int result = new Solution().fib(num);
        Instant finish = Instant.now();
        long timeElapsed = Duration.between(start, finish).toMillis();
        System.out.println("fib(" + num + ") = " + result + ",Total time taken = " + timeElapsed);
      }
   }
   public int fib(int n) { 
      int[] dp = new int[n+1];
      dp[1]=1;
      for(int i=0; i<=n; i++) {
        if(i+1 <= n) {
           dp[i+1] += dp[i];
        }
        if(i+2 <= n) {
           dp[i+2] += dp[i];
        }
      }
      return dp[n];
   }
}

Sample Output

fib(3) = 2,Total time taken = 0
fib(4) = 3,Total time taken = 0
fib(40) = 102334155,Total time taken = 0
fib(45) = 1134903170,Total time taken = 0

Time Complexity And Space Complexity

This iterative solution will execute n+1 number of times and hence

Time Complexity is ~O(n)

Space Complexity is ~O(n) for storing the values.

This is bottom up approach of dynamic programming.

Happy Coding.

Enjoy!!!