Fibonacci Sequence (DP)
The Fibonacci sequence is computed efficiently using dynamic programming techniques like memoization (top-down) or tabulation (bottom-up), reducing exponential time complexity O(2^n) to linear O(n). This classic example demonstrates how DP avoids redundant calculations by storing previously computed values.
Visualization
Interactive visualization for Fibonacci Sequence (DP)
Fibonacci Sequence (DP)
• Time: O(n) with DP
• Space: O(n) - can be optimized to O(1)
• F(n) = F(n-1) + F(n-2)
Interactive visualization with step-by-step execution
Implementation
1// DP solution
2function fibonacci(n: number): number {
3 if (n <= 1) return n;
4
5 const dp: number[] = [0, 1];
6 for (let i = 2; i <= n; i++) {
7 dp[i] = dp[i - 1] + dp[i - 2];
8 }
9
10 return dp[n];
11}
12
13// Space optimized
14function fibonacciOptimized(n: number): number {
15 if (n <= 1) return n;
16
17 let prev = 0, curr = 1;
18 for (let i = 2; i <= n; i++) {
19 [prev, curr] = [curr, prev + curr];
20 }
21
22 return curr;
23}
24
25// Matrix exponentiation O(log n)
26function fibonacciMatrix(n: number): number {
27 if (n <= 1) return n;
28
29 const multiply = (a: number[][], b: number[][]): number[][] => {
30 return [
31 [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
32 [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
33 ];
34 };
35
36 const power = (m: number[][], n: number): number[][] => {
37 if (n === 1) return m;
38 if (n % 2 === 0) {
39 const half = power(m, n / 2);
40 return multiply(half, half);
41 }
42 return multiply(m, power(m, n - 1));
43 };
44
45 const result = power([[1, 1], [1, 0]], n);
46 return result[0][1];
47}Deep Dive
Theoretical Foundation
The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ...) is defined as F(n) = F(n-1) + F(n-2) with base cases F(0)=0 and F(1)=1. Naive recursion recalculates the same values exponentially many times, resulting in O(2^n) complexity. Dynamic Programming optimizes this using two approaches: Memoization (top-down with caching) stores results in a hash map/array during recursion, while Tabulation (bottom-up) iteratively fills an array from base cases upward. Both achieve O(n) time and O(n) space. Further optimization using only two variables reduces space to O(1).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(n) or O(1) optimized
Applications
Industry Use
Algorithm analysis and time complexity teaching
Nature patterns (flower petals, spiral shells)
Financial modeling (compound interest)
Computer graphics (recursive subdivision)
Data structure design (Fibonacci heaps)
Network optimization (Fibonacci search)
Use Cases
Related Algorithms
0/1 Knapsack Problem
A classic optimization problem where you must select items with given weights and values to maximize total value without exceeding the knapsack's capacity. Each item can be taken only once (0 or 1). This is a fundamental problem in combinatorial optimization, resource allocation, and decision-making scenarios.
Longest Common Subsequence (LCS)
Finds the longest subsequence common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is fundamental in diff utilities, DNA sequence analysis, and version control systems like Git.
Edit Distance (Levenshtein Distance)
Edit Distance, also known as Levenshtein Distance, computes the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. Named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, this fundamental algorithm has applications in spell checking, DNA sequence analysis, natural language processing, and plagiarism detection.
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) finds the length of the longest subsequence in an array where all elements are in strictly increasing order. Unlike a subarray, a subsequence doesn't need to be contiguous - elements can be selected from anywhere as long as their order is preserved. This classic DP problem has two solutions: O(n²) dynamic programming and O(n log n) binary search with patience sorting. Applications include stock price analysis, scheduling, Box Stacking Problem, and Building Bridges Problem.