Dynamic Programming

Dynamic Programming solves complex problems by breaking them into simpler subproblems and storing results to avoid redundant calculations.

Animated Visualization

Step 1 of 7

DP Base Cases: F(0) = 0, F(1) = 1 (memoization table initialized)

javascript

← Scroll →

// Fibonacci - Naive Recursive (O(2ⁿ))
function fibonacciNaive(n) {
  if (n <= 1) return n;
  return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}
// Fibonacci - Memoization (Top-down DP) - O(n)
function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}
// Fibonacci - Tabulation (Bottom-up DP) - O(n)
function fibonacciTab(n) {
  if (n <= 1) return n;
  
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
// Fibonacci - Space Optimized - O(n) time, O(1) space
function fibonacciOptimized(n) {
  if (n <= 1) return n;
  
  let prev2 = 0;
  let prev1 = 1;
  
  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}
// Time Complexity:
// Naive: O(2ⁿ) - Exponential
// Memoization: O(n) - Linear
// Tabulation: O(n) - Linear
// Optimized: O(n) time, O(1) space

Swipe horizontally to view full code

Explanation

Dynamic Programming optimizes recursive solutions by storing results of subproblems (memoization/tabulation). This transforms exponential time complexity (O(2ⁿ)) to linear (O(n)) for problems like Fibonacci. DP solves overlapping subproblems efficiently.

Operations & Complexity

MemoizationO(n)

Top-down, cache results

TabulationO(n)

Bottom-up, build table

Space OptimizedO(1)

Use only necessary variables

Naive RecursiveO(2ⁿ)

Exponential, redundant calculations

Time Complexity