← Index

Dynamic Programming

Dynamic Programming

Cache overlapping subproblem results so you never recompute them.

What it is

DP applies when a problem breaks into subproblems that overlap — the same smaller calculation gets needed again and again (naive recursive fibonacci recomputes fib(2) hundreds of times for fib(30)). Cache each subproblem's result the first time it's solved, either top-down (memoization, recursion + a cache) or bottom-up (tabulation, an iterative table built from the base case up).

Real-world examples

• A restaurant kitchen prepping common sauce bases once each morning instead of remaking the same base sauce from scratch for every single dish that uses it.
• Keeping sticky notes of answers you've already worked out during a math test, instead of redoing the same sub-calculation every time it reappears in a later question.

Where you've probably used this already

• React's useMemo/useCallback — caching expensive computed values across renders is the exact same idea as memoization.
• HTTP/CDN caching and memoized database queries — don't redo expensive work you already have the answer to.
• 'Coin change', 'climbing stairs', 'longest common subsequence' — the DP interview staples, all overlapping-subproblem shaped.

Complexity

Code

// Dynamic Programming — solve a problem by breaking it into overlapping
// subproblems and CACHING their results, so you never recompute the
// same thing twice. Two flavors: top-down (memoization) and bottom-up
// (tabulation). Both shown below.

// --- Naive recursive fibonacci: O(2^n), recomputes the same values ---
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
}

// --- Top-down with memoization: O(n) ---
function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n);
  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

// --- Bottom-up with tabulation: O(n), no recursion/call stack risk ---
function fibTabulation(n) {
  if (n <= 1) return n;
  const table = [0, 1];
  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

// --- Classic DP interview problem: climbing stairs ---
// You can climb 1 or 2 steps at a time — how many distinct ways to
// reach step n? (Same recurrence shape as fibonacci.)
function climbStairs(n, cache = new Map()) {
  if (n <= 2) return n;
  if (cache.has(n)) return cache.get(n);
  const result = climbStairs(n - 1, cache) + climbStairs(n - 2, cache);
  cache.set(n, result);
  return result;
}

// --- Classic DP problem: coin change (fewest coins to make an amount) ---
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins needed to make amount 0

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], dp[a - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// --- Example Usage ---
console.log("fibMemo(30):", fibMemo(30));           // 832040, instant
// fibNaive(30) works too but is noticeably slower — try fibNaive(40) and feel it
console.log("fibTabulation(10):", fibTabulation(10)); // 55
console.log("climbStairs(5):", climbStairs(5));       // 8
console.log("coinChange([1,5,10,25], 63):", coinChange([1, 5, 10, 25], 63)); // 6

// The "cache expensive repeated work" idea shows up everywhere:
// - React's useMemo / useCallback
// - HTTP caching, memoized DB queries
// - CSS layout engines caching computed styles between renders