Lesson 06-Dynamic Programming

What is Dynamic Programming?

Let me start with a story. When I first encountered Dynamic Programming (DP), I thought it sounded incredibly boring. “Dynamic Programming”—really? It sounds like something from a 1970s textbook on COBOL.

But then I started solving problems with it, and my mind was blown. Dynamic Programming is like having a superpower: the ability to break seemingly impossible problems into small, manageable pieces, and then reuse your work to build the solution.

Here’s the formal definition: Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their solutions to avoid redundant computation.

That’s a mouthful. Let me translate it into plain English:

Dynamic Programming = Divide and Conquer + Memoization

You break the problem into subproblems (like divide and conquer), but unlike divide and conquer, the subproblems overlap. So you store the results of subproblems so you don’t solve them again.

When to Use Dynamic Programming

Not every problem can be solved with DP. To use DP, the problem must have two properties:

1. Optimal Substructure: The optimal solution to the problem contains optimal solutions to its subproblems. Example: The shortest path from A to C is the shortest path from A to B plus the shortest path from B to C (for some intermediate point B).
2. Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times. Example: In Fibonacci, F(5) = F(4) + F(3). But F(4) = F(3) + F(2). Notice that F(3) is computed twice! That’s overlapping subproblems.

Let me show you a problem that does NOT have these properties: Binary Search. Why? Because the subproblems don’t overlap. When you search the left half, you never need to search the right half again. So Binary Search is divide and conquer, but it’s NOT Dynamic Programming.

The Two Approaches: Top-Down vs Bottom-Up

There are two main ways to implement DP:

1. Top-Down (Memoization): Start with the original problem. Break it into subproblems. If you’ve already solved a subproblem, return the cached result. This is recursion + memoization.
2. Bottom-Up (Tabulation): Start with the smallest subproblems. Solve them and store the results. Build up to larger subproblems until you solve the original problem. This is iteration + table-filling.

Let me illustrate with Fibonacci:

Top-Down Approach (Memoization):

function fibonacciTopDown(n, memo = new Map()) {
  // Base cases
  if (n <= 1) return n;
  
  // Check if we've already computed this
  if (memo.has(n)) {
    return memo.get(n);
  }
  
  // Compute and store the result
  const result = fibonacciTopDown(n - 1, memo) + fibonacciTopDown(n - 2, memo);
  memo.set(n, result);
  
  return result;
}

function fibonacciTopDown(n, memo = new Map()) {
  // Base cases
  if (n <= 1) return n;
  
  // Check if we've already computed this
  if (memo.has(n)) {
    return memo.get(n);
  }
  
  // Compute and store the result
  const result = fibonacciTopDown(n - 1, memo) + fibonacciTopDown(n - 2, memo);
  memo.set(n, result);
  
  return result;
}

Bottom-Up Approach (Tabulation):

function fibonacciBottomUp(n) {
  if (n <= 1) return n;
  
  // Create a table to store results
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  // Fill the table bottom-up
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

function fibonacciBottomUp(n) {
  if (n <= 1) return n;
  
  // Create a table to store results
  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  // Fill the table bottom-up
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

Both approaches give the same result, but they have different characteristics:

• Top-Down: Easier to implement (closer to the mathematical definition). Uses recursion (which can cause stack overflow). Only computes the subproblems that are needed.
• Bottom-Up: A bit harder to implement (you need to figure out the order of computation). Uses iteration (no stack overflow). Computes all subproblems, even ones that might not be needed.