Dynamic Programming Fibonacci Sequence

Question

I was learning dynamic programming's application to the Fibonacci Sequence and had a question. Here is the code for reference:

import java.math.BigInteger;
import java.util.Arrays;

public class FibonacciNumbersB {

    static BigInteger[] dp = new BigInteger[10000];

    public static void main(String[] args) {
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;

        for(int i = 4; i < 9999; i++)
            System.out.println(fibRecurse(i).toString());
    }

    public static BigInteger fibRecurse(int N) {
        for(int i = 2; i < N; i++) {
            // For numerous calls to this function, this will save as it goes
            if(dp[i].equals(BigInteger.ZERO))
                dp[i] = dp[i - 1].add(dp[i - 2]);
        }

        return dp[N - 1];
    }
}

I have a statement check if dp[i] equals 0 in the fibRecurse method (although fibRecurse isn't recursive).

Is it more efficient to check if dp[i] has been calculated already or to just let dp[i] equal to the sum of the previous two elements?

Is it more effective to even check for null or recalculate dp[i]? @ElliottFrisch — Imagine Dragons
– Imagine Dragons, Commented Apr 17, 2017 at 0:33
Benchmark your code. But this is not a recursive algorithm, and your memoization isn't going to help. — Elliott Frisch
– Elliott Frisch, Commented Apr 17, 2017 at 0:35
Maybe i don't understand your question, but checking the value first would be more efficient rather than always recalculating - for large inputs at least. Isn't that the whole point of dynamic programming? — Christian
– Christian, Commented Apr 17, 2017 at 0:40
@Chris Oh I see. Thanks for your reply - that's what I was looking for. — Imagine Dragons
– Imagine Dragons, Commented Apr 17, 2017 at 0:54
no problem. dynamic programming is pretty similar to some other "algorithm types" out there. I think of it kind of like divide and conquer, but you save the "sub-problems" to a solution with the intent of possibly reusing them. hope that helps a bit — Christian
– Christian, Commented Apr 17, 2017 at 5:44

Elliott Frisch · Accepted Answer · 2017-04-17 01:24:09Z

3

I would prefer a Map<Integer, BigInteger> over using a fixed BigInteger[] when performing this memoization. Note that your current approach is not recursive. The Map might be declared and initialized like

static Map<Integer, BigInteger> memo = new HashMap<>();
static {
    memo.put(0, BigInteger.ONE);
    memo.put(1, BigInteger.ONE);
}

Then check if the current n is present in the memo (if it is, return it) - otherwise, computer and store it. Like,

public static BigInteger fibRecurse(int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    memo.put(n, v);
    return v;
}

A version without memoization would simply omit memo like

public static BigInteger fibRecurseSlow(int n) {
    if (n == 0 || n == 1) return BigInteger.ONE;
    BigInteger v = fibRecurse(n - 1).add(fibRecurse(n - 2));
    return v;
}

I think you can infer from the method names I've chosen which is slower.

answered Apr 17, 2017 at 1:24

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

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

1 Comment

Imagine Dragons Over a year ago

Perfect, it makes sense. I always thought using a Map<A, B> wouldn't be O(1) lookup.

Mattia Dinosaur · Accepted Answer · 2017-04-17 04:00:25Z

1

import java.math.BigInteger;
import java.util.Arrays;

public class FibonacciNumbersB {

    static BigInteger[] dp = new BigInteger[10000];

    public static void main(String[] args) {
        dp[0] = BigInteger.ONE;
        dp[1] = BigInteger.ONE;
        int N = 9999;
         fibRecurse(N);
        for(int i = 0; i < N; i++)
            System.out.println(dp[i].toString()) ;
    }

    public static void fibRecurse(int N) {
        for(int i = 2; i < N; i++) {

                dp[i] = dp[i - 1].add(dp[i - 2]);
        }
    }
}

edited Apr 17, 2017 at 4:00

answered Apr 17, 2017 at 1:17

Mattia Dinosaur

92011 silver badges30 bronze badges

7 Comments

Imagine Dragons Over a year ago

Is this not slower than the method above?

Mattia Dinosaur Over a year ago

time complexity is the same as @Elliott Frisch answer which is O(n)

Imagine Dragons Over a year ago

But for numerous calls you have to repeat the calculation whereas @Elliot Frisch does not have to.

Mattia Dinosaur Over a year ago

after the function fibRecurse(N) , i have caculate all from 1th to Nth and save them into array.

Imagine Dragons Over a year ago

Will you not still be calculating the sum over and over again?

|

Gayan Sampath · Accepted Answer · 2018-07-26 15:07:31Z

The code that is for finding fibonacci sequence can be write easily.Let's consider recursive code for finding fibonacci number set.

import java.util.Scanner;

class fac{
  public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    System.out.print(fibonacci(n));
}   

public static int fibonacci(int x){
    if(x<2){
        return 1;
    }
    else{
        return (fibonacci(x-1)+fibonacci(x-2));
    }
}

}

In this stage, there are many same subproblems are calculating again and again.So in this case, time complexity goes to height for large input. Because of that reason , dynamic programming technique was came ...In dynamic programming ,an extra table('lookUp' table) is maintained for storing previous calculated subproblems' values. before calculating next subproblems' value, check whether availability of the answer for the particular subproblem in created table('lookUp' table).If it is in the 'lookUp table', get the answer for particular subproblem. If it is not in the 'lookUp ' table, calculate value of the particular problem and store the 'lookUp ' table. That is the meaning of the dynamic programming technique.There are two ways for performing this technique.

1.Memoization - memoization is the technique that calculating values of subproblems Top- Down manner.Let's consider the code of fibonacci sequence.

 import java.util.Scanner;

 class fab{
   public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    int[] lookUp=new int[n];        
    int i;

    for(i=0;i<n;i++){
        lookUp[i]=-1;
    }
    fibonachi(n);   
}
public static void fibonachi(int x){
    if(lookUp[x]==-1){
        if(x<=1){
            lookUp[x]=x;
        }
        else{
            lookUp[x]=fibonachi(x-1)+fibonachi(x-2);
        }
    }
    System.out.print(lookUp[x]);
}

}

2.Tabulation - This calculation goes to Bottom to Top manner.At first consider the base case and perform . Then perform the next steps using previous cases.Les's consider fibonacci sequence code with tabulation technique.

import java.util.Scanner;

class fac{
  public static void main(String a[]){

    Scanner sc=new Scanner(System.in);
    System.out.print("Enter Your number :");
    int n=sc.nextInt();

    int[] lookUp=new int[n];        
    int i;

    lookUp[0]=1; // store base case values in the 'lookUp' table
    lookUp[1]=1;

    for(i=2;i<n;i++){
        lookUp[i]=lookUp[i-1]+lookUp[i-2];
    }
    System.out.print(lookUp[n-1]);
  }

}

In this case , base case values are stored at first.then calculates next values using previous ones..In tabulation all the values must be calculated because new value calculated using previous vlues..so memoization is better than tabulation.That's all. I hope, you could get idea.Thank you!

Collectives™ on Stack Overflow

Dynamic Programming Fibonacci Sequence

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related