Dynamic Programming: Memoization (Top-Down)

1. Two Roads to Dynamic Programming: Top-Down vs. Bottom-Up

Dynamic Programming problems can generally be solved in two ways:

1. Top-Down with Memoization: This approach feels very natural. You start with the original problem and break it down recursively. The "memoization" part means you store the results of subproblems as you solve them, so you never have to solve the same one twice.
2. Bottom-Up with Tabulation: This approach is typically iterative. You start by solving the smallest possible subproblems and use their solutions to build up answers to larger and larger subproblems until you arrive at the solution for the original problem.

2. The Problem with Naive Recursion: Fibonacci's Redundant Work

Let's use the classic Fibonacci sequence to see why a naive recursive solution is often a terrible idea. The definition is simple:

A direct translation into a recursive function seems straightforward. But what happens when we try to compute fib(5)? Let's see the explosion of redundant calculations.

As the video demonstrates, the number of function calls grows exponentially. The time complexity is $O(2^n)$, which becomes unfeasibly slow for even moderately large values of $n$. This is the problem that memoization solves.

3. The Solution: Memoization

Memoization is a simple but powerful idea: "Don't re-compute what you've already solved."

We'll use a data structure—often an array or a hash map—to act as a "memo" or cache. When our function is asked to solve for a value n, it first checks the memo:

• If the result for n is already there, it returns the cached value instantly.
• If not, it computes the result, stores it in the memo, and then returns it.

This process effectively "prunes" the recursion tree, eliminating all redundant branches.

4. A Step-by-Step Guide to Implementing Memoization

You can systematically convert almost any naive recursive solution for a DP problem into a memoized one. This recipe is a key takeaway for you to apply to other problems.

To get a clear understanding of these steps, watch the next part of the video.

Here is a summary of the three key steps to transform a pure recursive function into a top-down DP solution:

1. Create a memoization table: Create a data structure (e.g., an array or hash map) to store the results of the subproblems. The size should correspond to the possible states of your problem. Initialize it with a sentinel value (like -1 or null) to indicate that a state has not yet been computed.
2. Add the memo check: At the top of your recursive function, immediately after the base cases, check if the solution for the current state is already in your memoization table. If it is (i.e., not the sentinel value), return the stored result immediately.
3. Store the result: If the result was not in the memo, compute it recursively as before. Then, just before returning the result, store it in the memoization table.

Let's see this in pseudocode for our Fibonacci example:

// Step 1: Initialize memo table
memo = array of size n+1, filled with -1

function fib(n):
  // Base cases
  if n <= 1:
    return n

  // Step 2: Check the memo
  if memo[n] != -1:
    return memo[n]

  // Compute the result if not in memo
  result = fib(n-1) + fib(n-2)

  // Step 3: Store the result before returning
  memo[n] = result
  return result

Complexity Analysis

• Time Complexity: $O(n)$. Each subproblem from fib(0) to fib(n) is computed exactly once. Subsequent calls are $O(1)$ lookups.
• Space Complexity: $O(n)$. We use an array of size n for the memoization table, and the depth of the recursion call stack will also be at most n.

We have traded memory for a massive reduction in computation time, from exponential to linear.

function factorial(n):
  if n == 0:
    return 1
  return n * factorial(n-1)

5. Generalizing the Pattern: Longest Common Subsequence (LCS)

The Fibonacci example uses a 1D memoization table. Let's look at a problem that requires a 2D table to generalize the pattern.

The Longest Common Subsequence (LCS) problem asks for the longest subsequence common to two sequences (e.g., two strings). For example, the LCS of "ABCBDAB" and "BDCABA" is "BCBA", which has a length of 4.

The first step, as always, is to define a recurrence relation.

As you can see from the resource, the memoized solution for LCS follows the same pattern:

1. Memo Table: A 2D array memo[n][m] is used because the subproblems are defined by two variables (the current lengths of the two strings).
2. Check Memo: The function checks memo[n][m] at the start.
3. Store Result: The computed result is stored in memo[n][m] before returning.

This reduces the time complexity from exponential to $O(n\times m)$, at the cost of $O(n\times m)$ space for the memoization table.

Conclusion

In this lesson, you've learned the theory and practice of the top-down dynamic programming approach. You can now transform an inefficient, naive recursive algorithm into an optimized one using memoization.

Key Takeaways:

• Memoization is a top-down DP technique that uses caching to avoid re-computing overlapping subproblems.
• The implementation follows a simple three-step pattern: create a memo table, check the table at the start of your function, and store the result before returning.
• This technique offers a significant time complexity improvement (often from exponential to polynomial) in exchange for increased space complexity. This time-space trade-off is a fundamental concept in system design and architecture.

Preview of the Next Lesson:

Now that you've mastered the top-down approach, what's next? In the next lesson, we will solve the same types of problems using the bottom-up approach, known as tabulation. You will learn to build your solution iteratively from the base cases up, often eliminating recursion entirely. This will give you another powerful tool for your algorithmic toolkit.