Fibonacci numbers are strongly related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of N and the golden ratio, and imply that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases. In his 1202 book Liber Abaci, Fibonacci introduced the sequence to Western European mathematics, although the sequence had been described earlier in Indian mathematics, as early as 200 BC in work by Pingala on enumerating possible shapes of Sanskrit poetry formed from syllables of two lengths. At the end of the nth month, the number of pairs of rabbits is equal to the number of mature pairs (that is, the number of pairs in month N – 2) plus the number of pairs alive last month (month N – 1). At the end of the fourth month, the original pair has produced yet another new pair, and the pair birth two months ago also produces their first pair, make 5 pairs. Fibonacci considers the increase of an idealized (biologically unrealistic) rabbit population, assume that: a newly birth breeding pair of rabbits are put in a field; each breeding pair mates at the age of one month, and at the end of their second month they always produce another pair of rabbits; and rabbits never die, but continue breeding forever.

COMING SOON!

```
package DynamicProgramming;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @author Varun Upadhyay (https://github.com/varunu28)
*/
public class Fibonacci {
private static Map<Integer, Integer> map = new HashMap<>();
public static void main(String[] args) {
// Methods all returning [0, 1, 1, 2, 3, 5, ...] for n = [0, 1, 2, 3, 4, 5, ...]
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(fibMemo(n));
System.out.println(fibBotUp(n));
System.out.println(fibOptimized(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
**/
public static int fibMemo(int n) {
if (map.containsKey(n)) {
return map.get(n);
}
int f;
if (n <= 1) {
f = n;
} else {
f = fibMemo(n - 1) + fibMemo(n - 2);
map.put(n, f);
}
return f;
}
/**
* 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
**/
public static int fibBotUp(int n) {
Map<Integer, Integer> fib = new HashMap<>();
for (int i = 0; i <= n; i++) {
int f;
if (i <= 1) {
f = i;
} else {
f = fib.get(i - 1) + fib.get(i - 2);
}
fib.put(i, f);
}
return fib.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)
**/
public static int fibOptimized(int n) {
if (n == 0) {
return 0;
}
int prev = 0, res = 1, next;
for (int i = 2; i <= n; i++) {
next = prev + res;
prev = res;
res = next;
}
return res;
}
}
```