//IK-FibanocciBottomUpOptimized DP approaches using DP

​

using System;

using System.Collections;

public class Program

{

    static Hashtable HashTableTopDownRecurssionandDP = new Hashtable();

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int n = 50;

        Console.WriteLine(fibannocciTCofNandSCofN(n));

        Console.WriteLine(fibannocciTCofNandSCofNWithSpaceOptimized(50));

        //Console.WriteLine(fibanocciTopDownRecurssionandDP(n));

        //Note

        //fib(0)= 0

    }

    //Bottom up, TC= O(n), SC= O(n) Non recurssive, Non optimized .Execute Time =0.016s

    //This is a DAG with Topologial sorting 

    static int fibannocciTCofNandSCofN(int n)

    {

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

        table[0] = 0;

        table[1] = 1;

        for(int i=2; i <=n ; ++i)

        {

            table[i] = table[i-1] + table[i-2];

        }

        return table[n];

    }

    //Bottom up, TC= O(n), SC= O(1) Non recurssive,  Optimized . FINAL APPROACH. Bottom up is preferred in interview

    static ulong fibannocciTCofNandSCofNWithSpaceOptimized(ulong n) // ulong 64bit unsigned integer

    {

        ulong[] table = new ulong[3];

        table[0] = 0;

        table[1] = 1;

        table[2] = 1;

        for(ulong i=3; i <=n ; ++i)

        {

            table[i%3] = table[(i-1)%3] + table[(i-2)%3];

            //Console.Write(i + "- ");

            //Console.WriteLine(table[i%3]);

        }

        return table[n%3];

    }

    //Recurssion, optimized with DP TC= O(n), SC= O(n) recurssive. Time =0.203 for n=100 

    static int fibanocciTopDownRecurssionandDP(int n)

    {

        if(HashTableTopDownRecurssionandDP.ContainsKey(n))

           return (int)HashTableTopDownRecurssionandDP[n];

        if(n==0 || n==1)

            return n;

         HashTableTopDownRecurssionandDP[n] =fibanocciTopDownRecurssionandDP(n-1) + fibanocciTopDownRecurssionandDP(n-2);

        return (int)HashTableTopDownRecurssionandDP[n];

    }

}