WikiGalaxy
Fibonacci Series Using Dynamic Programming
Introduction
The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Dynamic Programming (DP) is an optimization technique that solves problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.
Basic Fibonacci using DP
In this approach, we use a simple array to store the Fibonacci numbers up to a desired index, thereby reducing the time complexity to O(n).
public class FibonacciDP {
public static int fibonacci(int n) {
if (n <= 1) return n;
int[] fib = new int[n + 1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Space Optimized Fibonacci
This method reduces space complexity to O(1) by using only two variables to store the last two Fibonacci numbers.
public class FibonacciSpaceOptimized {
public static int fibonacci(int n) {
if (n <= 1) return n;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Recursive Fibonacci with Memoization
Memoization stores the results of expensive function calls and reuses them when the same inputs occur again, thus optimizing recursive solutions.
import java.util.HashMap;
public class FibonacciMemoization {
private static HashMap memo = new HashMap<>();
public static int fibonacci(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);
return result;
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Matrix Exponentiation Method
This advanced method uses matrix exponentiation to compute the nth Fibonacci number in logarithmic time, making it highly efficient for large n.
public class FibonacciMatrix {
private static void multiply(int F[][], int M[][]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x; F[0][1] = y;
F[1][0] = z; F[1][1] = w;
}
private static void power(int F[][], int n) {
if (n == 0 || n == 1) return;
int M[][] = {{1, 1}, {1, 0}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0) multiply(F, M);
}
public static int fibonacci(int n) {
int F[][] = {{1, 1}, {1, 0}};
if (n == 0) return 0;
power(F, n - 1);
return F[0][0];
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
Using Binet's Formula
Binet's formula provides a closed-form expression to calculate the nth Fibonacci number using the golden ratio, though it's less precise for large n due to floating-point arithmetic.
public class FibonacciBinet {
public static int fibonacci(int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n) / Math.sqrt(5));
}
public static void main(String[] args) {
System.out.println(fibonacci(10));
}
}
