Fibonacci Series using Dynamic Programming

Question

Let us consider the implementation of Fibonacci series using dynamic programming.

// Fibonacci Series using Dynamic Programming
class fibonacci
{
static int fib(int n)
{
    /* Declare an array to store Fibonacci numbers. */
int f[] = new int[n+1];
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
   /* Add the previous 2 numbers in the series
     and store it */
    f[i] = f[i-1] + f[i-2];
}

return f[n];
}

public static void main (String args[])
{
    int n = 9;
    System.out.println(fib(n));
}
}

We use the dynamic programming so that the repetition of the recursive work does not occur. But here when every time the function has been called,a new array will be generated. So how could this algorithm is said to be more optimized ?

Everytime ? . I guess the array will be created once per function call. Suppose you want to find 100th fibonacci number. So an array of 100 will be created only once to store the numbers. — FallAndLearn
– FallAndLearn, Commented Jun 17, 2016 at 5:24
If you don't want the array to be created each time you call fib, don't create it in fib. — zmbq
– zmbq, Commented Jun 17, 2016 at 5:25
Also, to add the recursive one will also take O(n) space as it creates a tree. — FallAndLearn
– FallAndLearn, Commented Jun 17, 2016 at 5:27
This is the solution from GeeksForGeeks. Observe the 6th line of the code. Each and every time a new array has been created for each separate function call — Soumya Kanti Naskar
– Soumya Kanti Naskar, Commented Jun 17, 2016 at 5:28
"More optimized" than what? Either this question is another "please write an efficient version of Fib", or it's asking to compare a version of Fibonacci that uses O(n) storage with an unspecified algorithm. — Paul Hankin
– Paul Hankin, Commented Jun 17, 2016 at 5:49

Thomas · Accepted Answer · 2016-06-17 06:00:13Z

3

one optimization would be only save the last 2 values instead of all results. You don't need to store all your results.

you also can write the fibonacci series recursively in O(n):

int fib(int n1, int n2, int counter)
{
    if(counter == 0)
    {
        return n2;
    }
    else
    {
        return fib(n2,n2 + n1,counter-1);
    }
}

//to start:
int result = fib(0,1,100); //gives you the 100 fibonacci value

This code runs recursively and is easy to read. You don't have to initialize an array or other stuff.

alternatively you can use the nonrecursive option:

int fib(int number)
{
    int n1 = 0;
    int n2 = 1;
    int temp;
    for(int i = 0; i< number;i++)
    {
        temp = n1 + n2;
        n1 = n2;
        n2 = temp;
    }
    return n2;
}

If you want to store your results, you have to initialize the array outside of your fib function:

// Fibonacci Series using Dynamic Programming
class fibonacci
{
    /* Declare an array to store Fibonacci numbers. */
    int f[];

    static void init(int n)
    {    /* 0th and 1st number of the series are 0 and 1*/
        f = new int[n+1];            
        f[0] = 0;
        f[1] = 1;
    }

    static int fib(int n)
    {
        int i;

        for (i = 2; i <= n; i++)
        {
           /* Add the previous 2 numbers in the series
             and store it */
            f[i] = f[i-1] + f[i-2];
        }

        return f[n];
    }

    public static void main (String args[])
    {
        int n = 9;
        init(n);
        System.out.println(fib(n));
    }
}

edited Jun 17, 2016 at 6:00

answered Jun 17, 2016 at 5:42

Thomas

2,2894 gold badges25 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Thomas Over a year ago

to save the results to an array only makes sense, if you use them later

Paul Hankin Over a year ago

This answers the question "how do I write an O(n) integer arithmetic operations, O(1) additional integer storage Fibonacci function", but I don't think that's what the question is.

Thomas Over a year ago

you are right... because of that I edited my answer thx @PaulHankin

atul sachan · Accepted Answer · 2020-03-26 09:49:09Z

We use Memoization to prevent further recursion with Dynamic Programming. Memoization is the way to store already calculated values ex - let say fib(m) for index m is calculated and stored in memoization table. Further in upcoming recursions if fib(m) reoccur for calculation, then we take it from memoization table instead of doing again fib(m-1)+fib(m-2) i.e. avoid unnecessary recursions...Note - this will keep the complexity linear i.e. O(n).

We can implement this memoization in many ways for faster search. However here for Fibonacci we can implement memoization as array. And yes memoization table will be initialized just once. Below code is illustration for above explanation -

Note - we have taken a variable "complexity" which will incremented whenever we cant find value in memoization table i.e. whenever we go for recursion..

package com.company.dynamicProgramming;

import java.math.BigInteger;

public class FibonacciByBigDecimal {


    static int complexity = 0;

    public static void main(String ...args) {

        int n = 200;
        BigInteger[] memoization = new BigInteger[n + 1];

        System.out.println("fibonacci of "+ n + " is : " + fibByDivCon(n, memoization));
        System.out.println("Complexity is "+complexity);

    }


    static BigInteger fibByDivCon(int n, BigInteger[] memoization){

        if(memoization[n]!=null){
            return memoization[n];
        }

        complexity++;      

        if (n == 1 || n== 2){
            memoization[n] = BigInteger.ONE;
            return BigInteger.ONE;
        }

        // creates 2 further entries in stack
        BigInteger fibOfn = fibByDivCon(n-1, memoization).add( fibByDivCon(n-2, memoization)) ;

        memoization[n] = fibOfn;

        return fibOfn;

    }

}

Above i am calculating Fibonacci number at index 200. When I ran above code the result is : -

fibonacci of 200 is : 280571172992510140037611932413038677189525
Complexity is 200

Process finished with exit code 0

Collectives™ on Stack Overflow

Fibonacci Series using Dynamic Programming

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related