Algorithms Lesson 12: Dynamic Programming

Dynamic programming breaks complex problems into overlapping sub-problems, solves each once, and stores the result. It converts exponential solutions into polynomial ones.

Fibonacci: Evolution of Solutions

// Naive recursion: O(2^n) — TERRIBLE
fib(40) takes seconds.

// Memoization (top-down DP): O(n)
function fib(n, memo = new Map()) {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return n;
  const result = fib(n-1, memo) + fib(n-2, memo);
  memo.set(n, result);
  return result;
}

// Tabulation (bottom-up DP): O(n) time, O(1) space
function fibDP(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Classic DP Problems

// Coin Change: min coins to make amount
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins needed for amount 0
  
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

coinChange([1,5,10,25], 36); // 3 (25+10+1)