When you first hear the term "Dynamic Programming," it sounds like some high-level academic concept reserved for PhDs in computer science. In reality, if you've ever used a cache to avoid hitting a slow API, you're already thinking in DP. At its core, dynamic programming is just the art of remembering the answer to a sub-problem so you don't have to calculate it a thousand times. It's about trading a bit of memory for a massive amount of speed.

The Recursive Rabbit Hole

Let's look at a classic problem: the Coin Change problem. Imagine you're writing a system for a vending machine that needs to find the absolute minimum number of coins to make a specific amount of change. You have a set of denominations, say [1, 5, 10, 25]. The "naive" way to solve this is to use recursion—you try every possible coin, subtract its value from the total, and call the function again on the remainder.

def min_coins_naive(coins, amount)
  return 0 if amount == 0
  return Float::INFINITY if amount < 0

  best = Float::INFINITY
  coins.each do |coin|
    result = min_coins_naive(coins, amount - coin)
    best = [best, result + 1].min if result != Float::INFINITY
  end
  best
end

This looks clean, right? But it's a performance nightmare. If you try to find the change for 50 cents, Ruby will spend an eternity calculating the same values over and over. To find the answer for 50, it calculates for 49, 45, 40, and 25. But then the 49-cent branch also calculates for 45, 40, and 25. You've built a massive, redundant tree of calculations. This is exponential time complexity, and in a production environment, this is where your app hangs and your server alerts start screaming.

Saving Work with Memoization

The first pattern we use to fix this is Memoization. This is the "top-down" approach. We keep the recursive structure because it's intuitive, but we add a "memo" (usually a Hash) to store the result of every amount we've already solved. Before we do any heavy lifting, we check: "Do I already know the answer for this amount?"

def min_coins_memo(coins, amount, memo = {})
  return 0 if amount == 0
  return Float::INFINITY if amount < 0
  return memo[amount] if memo.key?(amount)

  best = Float::INFINITY
  coins.each do |coin|
    result = min_coins_memo(coins, amount - coin, memo)
    best = [best, result + 1].min if result != Float::INFINITY
  end

  memo[amount] = best
end

By adding that memo hash, you've fundamentally changed the complexity from exponential to linear relative to the amount. Now, each unique amount is calculated exactly once. I usually prefer memoization when the "state space" is sparse—meaning there are many possible sub-problems, but your specific input only requires a small fraction of them to be solved.

Building from the Ground Up

Then there's Tabulation, the "bottom-up" approach. Instead of starting at the target amount and drilling down, we start at 0 and build our way up to the target. We use an array (the table) to store the minimum coins for every value from 0 up to our target.

def min_coins_tab(coins, amount)
  # Initialize table with a value larger than any possible answer
  table = Array.new(amount + 1, Float::INFINITY)
  table[0] = 0

  (1..amount).each do |i|
    coins.each do |coin|
      if i - coin >= 0
        table[i] = [table[i], table[i - coin] + 1].min
      end
    end
  end

  table[amount] == Float::INFINITY ? -1 : table[amount]
end

This approach is often faster in Ruby because it avoids the overhead of recursive method calls and the risk of a SystemStackError (stack overflow) if the amount is very large. You're just iterating through an array. It's predictable and efficient.

Choosing Your Weapon

So, when do you use which? If I'm prototyping or dealing with a problem where I don't know which sub-problems will actually be hit, I go with memoization. It's more natural to write and only computes what it needs. However, if I'm writing a performance-critical utility where I know I'll need to solve almost every sub-problem anyway, I'll switch to tabulation. It's more robust against deep recursion and generally has a smaller memory footprint than a Hash. The trade-off is always between the intuitive "top-down" flow and the raw "bottom-up" efficiency.

📋 Practical Task

Implement a Longest Common Subsequence Solver

Your task is to implement a method longest_common_subsequence(str1, str2) that finds the length of the longest sequence of characters that appear in both strings in the same relative order (though not necessarily contiguously). For example, the LCS of "ABCDE" and "ACE" is 3 ("ACE").

To ensure you've mastered the DP patterns, you must implement this using the Tabulation (bottom-up) approach. Create a 2D array (a matrix) where matrix[i][j] represents the LCS of the first i characters of str1 and the first j characters of str2.

• Requirement 1: The method should return an integer representing the length of the LCS.
• Requirement 2: Use a 2D array to build the solution from the ground up.
• Requirement 3: Handle edge cases where one or both strings are empty.