Fibonacci Sequence & Intro to Dynamic Programming Code Implementations
Complete Fibonacci Sequence & Intro to Dynamic Programming code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Fibonacci Sequence & Intro to Dynamic Programming Guide · Launch Interactive Visualizer
C++ Implementation
// Fibonacci Sequence Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <chrono>
class Fibonacci {
public:
// Recursive Fibonacci (exponential time)
static long long fibonacciRecursive(int n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// Fibonacci with memoization (top-down DP)
static long long fibonacciMemo(int n) {
std::unordered_map<int, long long> memo;
return fibonacciMemoHelper(n, memo);
}
private:
static long long fibonacciMemoHelper(int n, std::unordered_map<int, long long>& memo) {
if (n <= 1) return n;
if (memo.find(n) != memo.end()) return memo[n];
long long result = fibonacciMemoHelper(n - 1, memo) + fibonacciMemoHelper(n - 2, memo);
memo[n] = result;
return result;
}
public:
// Fibonacci with tabulation (bottom-up DP)
static long long fibonacciTabulation(int n) {
if (n <= 1) return n;
std::vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space-optimized Fibonacci (O(1) space)
static long long fibonacciOptimized(int n) {
if (n <= 1) return n;
long long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long long next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with matrix exponentiation (O(log n) time)
static long long fibonacciMatrix(int n) {
if (n <= 1) return n;
std::vector<std::vector<long long>> matrix = {{1, 1}, {1, 0}};
std::vector<std::vector<long long>> result = matrixPower(matrix, n - 1);
return result[0][0];
}
private:
static std::vector<std::vector<long long>> multiply(
const std::vector<std::vector<long long>>& a,
const std::vector<std::vector<long long>>& b) {
return {
{a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]},
{a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]}
};
}
static std::vector<std::vector<long long>> matrixPower(
const std::vector<std::vector<long long>>& matrix, int power) {
if (power == 0) return {{1, 0}, {0, 1}};
if (power == 1) return matrix;
if (power % 2 == 0) {
std::vector<std::vector<long long>> half = matrixPower(matrix, power / 2);
return multiply(half, half);
} else {
return multiply(matrix, matrixPower(matrix, power - 1));
}
}
public:
// Fibonacci sequence generator
static std::vector<long long> fibonacciSequence(int n) {
std::vector<long long> sequence(n + 1);
for (int i = 0; i <= n; i++) {
sequence[i] = fibonacciOptimized(i);
}
return sequence;
}
// Fibonacci with modulo (for large numbers)
static long long fibonacciModulo(int n, long long mod) {
if (n <= 1) return n;
long long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long long next = (prev + curr) % mod;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with different bases
static long long fibonacciBase(int n, long long base) {
if (n <= 1) return n;
long long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long long next = (prev + curr) % base;
prev = curr;
curr = next;
}
return curr;
}
// Performance comparison
static void comparePerformance(int n) {
auto start = std::chrono::high_resolution_clock::now();
long long result1 = fibonacciOptimized(n);
auto end = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
start = std::chrono::high_resolution_clock::now();
long long result2 = fibonacciMatrix(n);
end = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Optimized: " << result1 << " (" << duration1.count() << " μs)" << std::endl;
std::cout << "Matrix: " << result2 << " (" << duration2.count() << " μs)" << std::endl;
}
};JAVA Implementation
// Fibonacci Sequence Implementation in Java
public class Fibonacci {
// Recursive Fibonacci (exponential time)
public static long fibonacciRecursive(int n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// Fibonacci with memoization (top-down DP)
public static long fibonacciMemo(int n) {
java.util.Map<Integer, Long> memo = new java.util.HashMap<>();
return fibonacciMemoHelper(n, memo);
}
private static long fibonacciMemoHelper(int n, java.util.Map<Integer, Long> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long result = fibonacciMemoHelper(n - 1, memo) + fibonacciMemoHelper(n - 2, memo);
memo.put(n, result);
return result;
}
// Fibonacci with tabulation (bottom-up DP)
public static long fibonacciTabulation(int n) {
if (n <= 1) return n;
long[] dp = new long[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space-optimized Fibonacci (O(1) space)
public static long fibonacciOptimized(int n) {
if (n <= 1) return n;
long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with matrix exponentiation (O(log n) time)
public static long fibonacciMatrix(int n) {
if (n <= 1) return n;
long[][] matrix = {{1, 1}, {1, 0}};
long[][] result = matrixPower(matrix, n - 1);
return result[0][0];
}
private static long[][] multiply(long[][] a, long[][] b) {
return new long[][]{
{a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]},
{a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]}
};
}
private static long[][] matrixPower(long[][] matrix, int power) {
if (power == 0) return new long[][]{{1, 0}, {0, 1}};
if (power == 1) return matrix;
if (power % 2 == 0) {
long[][] half = matrixPower(matrix, power / 2);
return multiply(half, half);
} else {
return multiply(matrix, matrixPower(matrix, power - 1));
}
}
// Fibonacci sequence generator
public static long[] fibonacciSequence(int n) {
long[] sequence = new long[n + 1];
for (int i = 0; i <= n; i++) {
sequence[i] = fibonacciOptimized(i);
}
return sequence;
}
// Fibonacci with modulo (for large numbers)
public static long fibonacciModulo(int n, long mod) {
if (n <= 1) return n;
long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long next = (prev + curr) % mod;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with different bases
public static long fibonacciBase(int n, long base) {
if (n <= 1) return n;
long prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
long next = (prev + curr) % base;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci using BigInteger for very large numbers
public static java.math.BigInteger fibonacciBigInteger(int n) {
if (n <= 1) return java.math.BigInteger.valueOf(n);
java.math.BigInteger prev = java.math.BigInteger.ZERO;
java.math.BigInteger curr = java.math.BigInteger.ONE;
for (int i = 2; i <= n; i++) {
java.math.BigInteger next = prev.add(curr);
prev = curr;
curr = next;
}
return curr;
}
}JAVASCRIPT Implementation
// Fibonacci Sequence Implementation in JavaScript
function fibonacciRecursive(n) {
if (n <= 1) return n;
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
// Fibonacci with memoization (top-down DP)
function fibonacciMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n] !== undefined) return memo[n];
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
// Fibonacci with tabulation (bottom-up DP)
function fibonacciTabulation(n) {
if (n <= 1) return n;
const dp = new Array(n + 1);
dp[0] = 0;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Space-optimized Fibonacci (O(1) space)
function fibonacciOptimized(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with matrix exponentiation (O(log n) time)
function fibonacciMatrix(n) {
if (n <= 1) return n;
function multiply(a, b) {
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
];
}
function matrixPower(matrix, power) {
if (power === 0) return [[1, 0], [0, 1]];
if (power === 1) return matrix;
if (power % 2 === 0) {
const half = matrixPower(matrix, power / 2);
return multiply(half, half);
} else {
return multiply(matrix, matrixPower(matrix, power - 1));
}
}
const baseMatrix = [[1, 1], [1, 0]];
const result = matrixPower(baseMatrix, n - 1);
return result[0][0];
}
// Fibonacci sequence generator
function fibonacciSequence(n) {
const sequence = [];
for (let i = 0; i <= n; i++) {
sequence.push(fibonacciOptimized(i));
}
return sequence;
}
// Fibonacci with modulo (for large numbers)
function fibonacciModulo(n, mod = 1000000007) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
const next = (prev + curr) % mod;
prev = curr;
curr = next;
}
return curr;
}
// Fibonacci with different bases
function fibonacciBase(n, base = 10) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
const next = (prev + curr) % base;
prev = curr;
curr = next;
}
return curr;
}PYTHON Implementation
# Fibonacci Sequence Implementation in Python
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# Fibonacci with memoization (top-down DP)
def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
# Fibonacci with tabulation (bottom-up DP)
def fibonacci_tabulation(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Space-optimized Fibonacci (O(1) space)
def fibonacci_optimized(n):
if n <= 1:
return n
prev, curr = 0, 1
for i in range(2, n + 1):
next_val = prev + curr
prev = curr
curr = next_val
return curr
# Fibonacci with matrix exponentiation (O(log n) time)
def fibonacci_matrix(n):
if n <= 1:
return n
def multiply(a, b):
return [
[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
]
def matrix_power(matrix, power):
if power == 0:
return [[1, 0], [0, 1]]
if power == 1:
return matrix
if power % 2 == 0:
half = matrix_power(matrix, power // 2)
return multiply(half, half)
else:
return multiply(matrix, matrix_power(matrix, power - 1))
base_matrix = [[1, 1], [1, 0]]
result = matrix_power(base_matrix, n - 1)
return result[0][0]
# Fibonacci sequence generator
def fibonacci_sequence(n):
sequence = []
for i in range(n + 1):
sequence.append(fibonacci_optimized(i))
return sequence
# Fibonacci with modulo (for large numbers)
def fibonacci_modulo(n, mod=1000000007):
if n <= 1:
return n
prev, curr = 0, 1
for i in range(2, n + 1):
next_val = (prev + curr) % mod
prev = curr
curr = next_val
return curr
# Fibonacci with different bases
def fibonacci_base(n, base=10):
if n <= 1:
return n
prev, curr = 0, 1
for i in range(2, n + 1):
next_val = (prev + curr) % base
prev = curr
curr = next_val
return curr
# Fibonacci using Python's built-in memoization
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_lru_cache(n):
if n <= 1:
return n
return fibonacci_lru_cache(n - 1) + fibonacci_lru_cache(n - 2)