Fibonacci DP

 

import java.util.Arrays;

public class Fibonacci_dp {

    /*
    Faith
    Recursive tree
    recursive code
    memoization
    observation
    tabulation
    optimization
    */


    public static void main(String[] args) {
        int n = 5;

        // Recursion
        System.out.println(fib(n));

        int[] dp = new int[n + 1];

        // Memoization
        Arrays.fill(dp, -1);
        System.out.println(fibMemo(n, dp));
        display(dp);

        // Tabulation
        Arrays.fill(dp, -1);
        System.out.println(fibTab(n, dp));
        display(dp);

    }


    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }

    public static int fibMemo(int n, int[] dp) {
        if (n <= 1) {
            //return n;
            return dp[n] = n;   // jo bhi return kr rha tha, usko store kiya hai
        }

        if (dp[n] != -1)
            return dp[n];

        //return  fibMemo(n - 1, dp) + fibMemo(n - 2, dp);
        // jo bhi return kr rha tha, usko store kiya hai
        return dp[n] = fibMemo(n - 1, dp) + fibMemo(n - 2, dp);
    }
  

    public static int fibTab(int N, int[] dp) {

        for (int n = 0; n <= N; n++) {
            if (n <= 1) {
                dp[n] = n;
                continue;
            }
            //if (dp[n] != -1) return dp[n];
            dp[n] = dp[n - 1] + dp[n - 2];  //return dp[n] = fibTab(n - 1, dp) + fibTab(n - 2, dp);
        }

        return dp[N];
    }


    public static void display(int[] dp) {
        for (int i : dp) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static void display2D(int[][] dp) {
        for (int[] i : dp) {
            for (int j : i) {
                System.out.print(j + "\t");
            }
            System.out.println();
        }
    }

}