Dynamic Programming Fibonacci Sequence

542
April 17, 2017, at 1:38 PM

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?

Answer 1

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.

Answer 2
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]);
        }
    }
}
Rent Charter Buses Company
READ ALSO
How and when to use loops? How to use methods? [on hold]

How and when to use loops? How to use methods? [on hold]

Can please explain to me how (i) all the different loops work (ie

271
Java 9 on Mac OS X Eclipse Neon Error &ldquo;Target is not a JDK root. System library was not found.&rdquo;

Java 9 on Mac OS X Eclipse Neon Error “Target is not a JDK root. System library was not found.”

Is it possible to use Java 9 as an Installed JRE in eclipse on OS X (El Capitan 1011

863
Best practice with regards to dynamically populated RecyclerView

Best practice with regards to dynamically populated RecyclerView

I have an application with a RecyclerView populated by an ArrayList which I scrape from a websiteAs I have it structured currently, the relevant fragment containing the RecyclerView contains an AsyncTask and thus the data is scraped in the fragment's...

341
Parsing Information From a File

Parsing Information From a File

I'm trying to read in information from a file in order to create a Graph using JavaI have the code below, however, after running the output is null

368