Memoization for Recursive Optimization

1. The Hallmarks of a Dynamic Programming Problem

Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solutions to its subproblems.

Not every recursive problem can be optimized with DP. A problem is a good candidate for DP if it exhibits two key properties:

1. Overlapping Subproblems: A recursive algorithm is said to have overlapping subproblems if it solves the same subproblem multiple times.
2. Optimal Substructure: A problem has an optimal substructure if an optimal solution to the problem can be constructed from the optimal solutions of its subproblems.

Let's see these properties in action with the classic Fibonacci sequence. The N-th Fibonacci number is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2), with base cases F(0) = 0 and F(1) = 1.

A direct recursive implementation in Java looks like this:

public int fib(int n) {
    // Base cases
    if (n <= 1) {
        return n;
    }
    // Recursive step
    return fib(n - 1) + fib(n - 2);
}

This is simple and correct, but it's incredibly inefficient. To understand why, let's visualize the recursive calls.

As you saw, calculating fib(5) involves calculating fib(3) twice, fib(2) three times, and so on. This redundancy leads to an exponential time complexity of roughly O(2ⁿ), which is unacceptably slow for even moderately large values of n.

2. The Solution: Memoization

The inefficiency comes from re-computing results we've already found. The solution is straightforward: remember the results. This is the essence of memoization.

Memoization is a top-down DP technique where we modify a recursive function to store the results of its computations in a data structure (like an array or a hash map), often called a "memo" or "cache". When the function is called again with the same inputs, it retrieves the stored result instead of re-computing it.

By storing the results, we ensure that the calculation for each Fibonacci number F(i) happens only once. This prunes the recursion tree, eliminating all the redundant branches.

3. A General Recipe for Memoization

The great thing about memoization is that it's a general pattern you can apply to any recursive function that has overlapping subproblems. Here's a three-step recipe to convert a plain recursive solution to a memoized one.

Let's formalize this recipe for a typical problem where the state can be represented by an integer n:

1. Create a "memo" storage: Create an array (e.g., int[] memo) of a size large enough to hold the results for all possible subproblems. The size is typically n+1. Initialize it with a value that signifies "not yet computed" (e.g., -1, 0, or null).
2. Add a "memo check": At the beginning of your recursive function, right after the base cases, check if the result for the current state is already in your memo. If it's not the "not yet computed" value, return it immediately.
3. Store the result: If the result was not in the memo, compute it using the original recursive logic. Then, just before returning the result, store it in your memo at the appropriate index.

Here is what the memoized Fibonacci code looks like in Java, following this recipe.

4. Complexity Analysis

By adding memoization, we've made a significant optimization.

• Time Complexity: Each subproblem fib(i) for i from 0 to n is now computed only once. Accessing and storing results in an array or hash map takes constant time on average. Therefore, the time complexity is reduced from O(2ⁿ) to O(n).
• Space Complexity: We use an array of size n to store the results. Additionally, due to the recursion, the call stack can go as deep as n. So, the total space complexity is O(n) for the memoization array + O(n) for the recursion stack, which is O(n).

int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

5. Applying the Recipe: The Coin Change Problem

Now let's apply our memoization recipe to a more typical interview problem: Coin Change.

Problem: Given an array of coin denominations and a total amount, find the minimum number of coins required to make up that amount. Assume you have an infinite supply of each coin.

For example, with coins {1, 5, 7} and an amount of 18, the minimum number of coins is 4 (one 7-coin, two 5-coins, one 1-coin).

A naive recursive approach would be:
minCoins(amount) = 1 + min( minCoins(amount - coin1), minCoins(amount - coin2), ... )

This has the same overlapping subproblems issue as Fibonacci. For example, minCoins(6) could be reached from 11 -> 6 (by using a 5-coin) or from 13 -> 6 (by using a 7-coin). We don't want to solve for minCoins(6) twice.

Let's watch how to apply our memoization recipe to this problem.

The key insight is that the state of our problem is defined by a single variable: the amount we need to make. Therefore, we can use a 1D array for our memoization table, just like we did with Fibonacci. This pattern of identifying the "state" of the recursion is crucial for solving DP problems.

Conclusion

Great work! You've just learned one of the most fundamental and useful techniques in dynamic programming. Memoization is a powerful tool for optimizing recursive algorithms and is a frequent topic in technical interviews.

Key Takeaways:

• Dynamic Programming is effective for problems with overlapping subproblems and optimal substructure.
• Memoization (Top-Down DP) is a technique where you store the results of expensive function calls and return the cached result when the same inputs occur again.
• You can convert a plain recursive function to a memoized one with a simple three-step recipe: create storage, check storage, and save the result.
• Memoization can drastically reduce time complexity, often from exponential to polynomial, at the cost of some extra space.

Preview of the Next Lesson:
Memoization elegantly optimizes recursion, but the recursive calls still have some overhead and can lead to stack overflow issues for very deep recursions. In the next lesson, we will learn how to convert our memoized, top-down solution into a purely iterative, bottom-up approach called tabulation. This will eliminate recursion entirely while still leveraging the core ideas of DP.