Fibonacci (DP)
Compute Fibonacci numbers efficiently using memoization or tabulation.
How it works
The Fibonacci sequence is the canonical introduction to Dynamic Programming because it exhibits both hallmarks of DP problems: optimal substructure (F(n) depends only on F(n-1) and F(n-2)) and overlapping subproblems (a naive recursive solution recomputes the same values exponentially many times — F(5) alone spawns 15 recursive calls). The DP approach eliminates this redundancy by solving each subproblem exactly once and storing the result.
This implementation uses the bottom-up tabulation style: it fills an array from F(0) upward, so every value needed for the next computation is already available. This avoids call-stack overhead entirely and makes memory access patterns cache-friendly. The result is O(n) time and O(n) space. A further optimization — the space-optimized variant — reduces memory to O(1) by keeping only the last two values, though it sacrifices the ability to answer arbitrary F(k) queries for k ≤ n in O(1).
Fibonacci DP is important beyond the sequence itself because it teaches the memoization pattern underpinning React's useMemo, HTTP response caches, LRU caches, and memoized selectors in Redux. It is also the foundation of more complex DP problems: Coin Change, Climbing Stairs, and many others reduce directly to Fibonacci-style recurrences once the state space is defined.
Complexity
Visualizer
Where it's used in the real world
React / frontend frameworks
useMemo and React.memo cache expensive derived valuesReact's memoization hooks apply exactly the DP insight: if the inputs haven't changed, return the cached result instead of recomputing. The underlying mechanism is a lookup table keyed on dependency values — a direct application of the tabulation pattern.
Financial modeling systems
Fibonacci retracement levels in technical analysis toolsTrading platforms precompute Fibonacci ratios (23.6%, 38.2%, 61.8%, 100%) from key price levels. Storing intermediate Fibonacci values in a lookup table lets analysts recompute price targets in O(1) as support/resistance levels shift — critical for real-time charting.
Fibonacci heap data structure
Amortized O(log n) decrease-key in Dijkstra's algorithmThe Fibonacci heap is named after the Fibonacci numbers because the sizes of its trees after consolidation follow the Fibonacci sequence. Understanding the DP properties of the sequence is essential for analyzing why decrease-key runs in O(1) amortized time.
Implementation
function fibonacciDP(n: number): number {
if (n <= 1) return n;
const table = new Array<number>(n + 1);
table[0] = 0;
table[1] = 1;
for (let i = 2; i <= n; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[n];
}
// Space-optimized O(1) variant
function fibonacciO1(n: number): number {
if (n <= 1) return n;
let [prev2, prev1] = [0, 1];
for (let i = 2; i <= n; i++) {
[prev2, prev1] = [prev1, prev2 + prev1];
}
return prev1;
}
console.log(fibonacciDP(10)); // 55
console.log(fibonacciO1(10)); // 55