Fibonacci.java

packagecom.thealgorithms.dynamicprogramming;

importjava.util.HashMap;
importjava.util.Map;
importjava.util.Scanner;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 */
publicclassFibonacci {

privatestaticMap<Integer, Integer> map = newHashMap<>();

publicstaticvoidmain(String[] args) {
// Methods all returning [0, 1, 1, 2, 3, 5, ...] for n = [0, 1, 2, 3, 4, 5, ...]
Scannersc = newScanner(System.in);
intn = sc.nextInt();

System.out.println(fibMemo(n));
System.out.println(fibBotUp(n));
System.out.println(fibOptimized(n));
System.out.println(fibBinet(n));
sc.close();
 }

/**
 * This method finds the nth fibonacci number using memoization technique
 *
 * @param n The input n for which we have to determine the fibonacci number
 * Outputs the nth fibonacci number
 */
publicstaticintfibMemo(intn) {
if (map.containsKey(n)) {
returnmap.get(n);
 }

intf;

if (n <= 1) {
f = n;
 } else {
f = fibMemo(n - 1) + fibMemo(n - 2);
map.put(n, f);
 }
returnf;
 }

/**
 * This method finds the nth fibonacci number using bottom up
 *
 * @param n The input n for which we have to determine the fibonacci number
 * Outputs the nth fibonacci number
 */
publicstaticintfibBotUp(intn) {
Map<Integer, Integer> fib = newHashMap<>();

for (inti = 0; i <= n; i++) {
intf;
if (i <= 1) {
f = i;
 } else {
f = fib.get(i - 1) + fib.get(i - 2);
 }
fib.put(i, f);
 }

returnfib.get(n);
 }

/**
 * This method finds the nth fibonacci number using bottom up
 *
 * @param n The input n for which we have to determine the fibonacci number
 * Outputs the nth fibonacci number
 * <p>
 * This is optimized version of Fibonacci Program. Without using Hashmap and
 * recursion. It saves both memory and time. Space Complexity will be O(1)
 * Time Complexity will be O(n)
 * <p>
 * Whereas , the above functions will take O(n) Space.
 * @author Shoaib Rayeen (https://github.com/shoaibrayeen)
 */
publicstaticintfibOptimized(intn) {
if (n == 0) {
return0;
 }
intprev = 0, res = 1, next;
for (inti = 2; i <= n; i++) {
next = prev + res;
prev = res;
res = next;
 }
returnres;
}

/**
 * We have only defined the nth Fibonacci number in terms of the two before it. Now, we will look at Binet's formula to calculate the nth Fibonacci number in constant time.
 * The Fibonacci terms maintain a ratio called golden ratio denoted by Φ, the Greek character pronounced ‘phi'.
 * First, let's look at how the golden ratio is calculated: Φ = ( 1 + √5 )/2 = 1.6180339887...
 * Now, let's look at Binet's formula: Sn = Φⁿ–(– Φ⁻ⁿ)/√5
 * We first calculate the squareRootof5 and phi and store them in variables. Later, we apply Binet's formula to get the required term.
 * Time Complexity will be O(1)
 */

publicstaticintfibBinet(intn) {
doublesquareRootOf5 = Math.sqrt(5);
doublephi = (1 + squareRootOf5)/2;
intnthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5);
returnnthTerm;
 }
}