Skip to content

Instantly share code, notes, and snippets.

@sdpatil
Created August 9, 2017 15:43
Show Gist options
  • Select an option

  • Save sdpatil/37e9f026e9e46a6e2cae9fd403db2089 to your computer and use it in GitHub Desktop.

Select an option

Save sdpatil/37e9f026e9e46a6e2cae9fd403db2089 to your computer and use it in GitHub Desktop.
Calculate fibonacci sequence number for given number n
import java.util.HashMap;
import java.util.Map;
/**
* Problem: Calculate fibonacci sequence number for given number n
* Ex. Fibonacci series generates numbers in the form n-1 + n-2
* 0 1 1 2 3 5 8 13 21 34
*/
public class Fibonacci {
private Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
//Basic brute force recursion
public int fibonacciRecursive(int n){
if(n <= 1)
return n;
else
return fibonacciNonRecursive(n-1) + fibonacci(n-2);
}
//This is memorized version
public int fibonacci(int n) {
if (n <= 1)
return n;
else if (!cache.containsKey(n)) {
cache.put(n, fibonacci(n - 1) + fibonacci(n - 2));
}
return cache.get(n);
}
//This is DP solution for fibonacci number
public int fibonacciNonRecursive(int n) {
if (n <= 1)
return n;
int fMinus2 = 0;
int fMinus1 = 1;
int nextNumber = 0;
for (int i = 2; i <= n; i++) {
nextNumber = fMinus2 + fMinus1;
fMinus2 = fMinus1;
fMinus1 = nextNumber;
}
return nextNumber;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment