Blueprint 14: "Remembering Past Solutions" 🧠

Blueprint 14: Remembering Past Solutions 🧠

Welcome, Architect. You've mastered recursion and divide and conquer, but some problems have a hidden trap: they force you to re-solve the same subproblems over and over, leading to massive inefficiency. You have reached the final and most powerful optimization paradigm. We will now learn to build solutions that learn from the past. This is Dynamic Programming (DP).

1. The Mission Briefing

The mission is to conquer problems that exhibit two specific traits: they can be broken down into smaller, similar pieces, and the solutions to these pieces are required many times. A naive recursive approach would be like an architect with amnesia, re-drafting the same small blueprint every time it's needed.

Dynamic Programming is the master technique of solving each unique subproblem only once, storing its result in memory, and simply looking it up the next time it's needed. It's about trading a little bit of space (to store solutions) for a massive gain in speed.

2. The Two Pillars of Dynamic Programming

A problem is a good candidate for a DP solution only if it meets two specific criteria:

• Overlapping Subproblems: The problem can be broken down into smaller subproblems that are reused multiple times. Consider calculating fib(5). This requires fib(4) and fib(3). But calculating fib(4) also requires fib(3). Without DP, we would compute fib(3) twice.
• Optimal Substructure: The optimal solution to the main problem can be constructed from the optimal solutions of its subproblems. (e.g., The shortest path from City A to City C that passes through City B is composed of the shortest path from A to B and the shortest path from B to C).

The classic example that demonstrates this perfectly is calculating Fibonacci numbers.

3. Approach 1: Memoization (Top-Down DP)

This is the most intuitive way to implement DP. It's the direct realization of the "sticky note" analogy. You write a standard recursive function, but you give it a memory (a cache, like an array or hash map) to store results. The process is:

1. Write the naive recursive solution.
2. Create a cache to store the results of subproblems. Initialize it with a sentinel value (like -1).
3. Inside the recursive function, before computing anything, check if the result for the current state is already in the cache. If it is, return the cached value immediately.
4. If it's not, compute the result as usual, but just before returning, save the result in the cache.

# 1. Create a cache to store results.
memo = {}

def fib(n):
  # 3. If the result is already in our cache, return it.
  if n in memo:
    return memo[n]
  
  # Base case
  if n <= 1:
    return n

  # 4. Compute the result as normal.
  result = fib(n - 1) + fib(n - 2)
  
  # 5. Before returning, save the result to the cache.
  memo[n] = result
  
  return result

4. Approach 2: Tabulation (Bottom-Up DP)

Tabulation takes the opposite approach. Instead of starting from the top and going down, it starts from the smallest possible subproblem and iteratively builds its way up to the original problem. It's like filling out a table (hence the name) from the beginning.

def fib(n):
    if n <= 1:
        return n
    
    # 1. Create a table of size n+1.
    table = [0] * (n + 1)

    # 2. Initialize the base cases.
    table[1] = 1

    # 3. Iterate and fill the table from the bottom up.
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]

    # 4. The final solution is the last entry.
    return table[n]

5. The Architect's Framework for DP

Dynamic Programming problems can be intimidating. Follow this systematic framework to deconstruct them.

1. Define the State: "What information do I need to store to solve this problem for a given input?" For Fibonacci, the state is simply the number n, so our table is dp[n]. For a knapsack problem, the state might be the current item i and the current weight capacity w, leading to a 2D table dp[i][w].
2. Find the Recurrence Relation: Express the solution for a given state in terms of previously solved, smaller states. For Fibonacci, the recurrence is fib(n) = fib(n-1) + fib(n-2).
3. Identify the Base Cases: What are the smallest subproblems you can solve directly? For Fibonacci, these are fib(0) = 0 and fib(1) = 1.

6. Classic DP Architecture: The 0/1 Knapsack Problem

Problem: You have a knapsack with a maximum weight capacity W, and a set of items, each with a given value and weight. You can either take an item or leave it. What is the maximum total value you can fit in the knapsack?