# 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?

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.

``````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]);
}
}
}
``````
POPULAR ONLINE

### 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 “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

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

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