Fibonacci

memoizationtabulationoverlapping-subproblems

Press play to start

1function fibonacci(n: number): number {
const dp: number[] = [0, 1]
for (let i = 2; i <= n; i++) {
  dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
7}

Step 1/0

Custom array:

Best:O(n)
Average:O(n)
Worst:O(n)
Space:O(n)

Computes Fibonacci numbers using memoization (top-down) or tabulation (bottom-up), showing how DP eliminates redundant computation.

Demonstrates the core DP concept. Memoization vs tabulation trade-offs apply to many optimization problems.