Implementing Top-Down Memoization

Welcome back! In our last lesson, we laid the conceptual groundwork for Dynamic Programming. We saw that the inefficiency in many naive recursive solutions comes from repeatedly solving the exact same subproblems. We then established a four-part framework—state, transition, base cases, and evaluation order—to reason about these problems systematically.

Today, we'll put that framework into action by implementing the most intuitive form of Dynamic Programming: top-down memoization. You'll see how to take a simple, brute-force recursive function and, with a few mechanical changes, make it incredibly efficient. This technique is a natural extension of the recursion skills you developed earlier in the course and is often the easiest way to start solving DP problems, which should help in building your confidence and overcoming any "algo phobia."

Your learning outcome for this lesson is to convert a repeated recursive subproblem into top-down memoization.

From Redundancy to Efficiency: The Core Idea

Let's revisit the Fibonacci sequence from our last discussion. The naive recursive implementation is elegant but slow because it creates a massive tree of calls, re-computing values like fib(2) multiple times.

function fib(n: number): number {
    if (n <= 1) {
        return n;
    }
    // This part causes redundant computations
    return fib(n - 1) + fib(n - 2);
}

Memoization tackles this inefficiency head-on with a simple strategy: caching. The first time we calculate the result for a subproblem (e.g., fib(3)), we store it in a lookup structure, like a hash map or an array. The next time we need that same result, we just fetch it from our cache instead of re-running the function.

This process transforms the explosive exponential recursion tree into a lean, linear set of calculations. Each subproblem is computed exactly once.

For a quick, high-level walkthrough of this concept, the following video explains the transition from a slow recursive function to a fast, memoized one.

The core logic you just saw can be summarized as:

1. Check: Before doing any work, check if the result for the current state is already in the cache. If it is, return it immediately.
2. Compute: If the result is not in the cache, compute it using the original recursive logic.
3. Store: Before returning the newly computed result, store it in the cache.

A Step-by-Step Recipe for Memoization

This "check-compute-store" pattern can be formalized into a reliable, step-by-step recipe. This is powerful because it allows you to first focus on getting the recursive logic correct (the brute-force solution) and then apply memoization as a separate, mechanical optimization step.

The following article from Yasir Tobbileh provides an excellent guide for this process.

Let's summarize the recipe you just read:

1. Make it work (Brute-force recursion): First, write a standard recursive solution. Don't worry about efficiency yet.
2. Make it efficient (Add memoization):
   a. Create a cache data structure (usually a Map or plain object in TypeScript/JavaScript).
   b. Pass this cache to all recursive calls.
   c. Add a new base case at the top of your function to check if the result for the current state is in the cache. If so, return it.
   d. Before returning the computed result from a recursive call, store it in the cache.

Applying the Recipe: Climbing Stairs

Let's apply this recipe to a classic problem: Climbing Stairs (LeetCode 70).

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1. Make it work (Brute-force):

   • State: The number of steps remaining, n.
   • Transition: From step n, you can get there from step n-1 (by taking 1 step) or from step n-2 (by taking 2 steps). So, ways(n) = ways(n-1) + ways(n-2).
   • Base Cases: ways(1) = 1, ways(2) = 2.
   • The recursive logic looks almost identical to Fibonacci.

2. Make it efficient (Memoization):
   Now, let's apply the memoization steps. We'll add a cache to store the number of ways for each n. The article you just looked at has a perfect walkthrough of this exact process.

As you can see, the code transformation is minimal, but the performance gain is huge—from exponential $O(2^n)$ to linear $O(n)$ time complexity, because we only compute ways(k) for each k from 1 to n once.

Handling Complex State as Cache Keys

So far, our state has been a single integer, n, which is easy to use as an array index or a map key. But what happens when the state is more complex? For example, in the "House Robber" problem, the state might be defined by the remaining subarray to consider. In other problems, a recursive function might take multiple arguments.

memo[...remainingArray] isn't a valid key for a JavaScript object. We need a way to convert the state—whatever it is—into a unique, string-based key. Your front-end development experience with data serialization is directly applicable here. The JSON.stringify() method is perfect for this.

Let's look at a practical problem that explores this idea: implementing a generic memoize higher-order function in JavaScript.

The key takeaway is that you can create a unique string representation of your function's arguments (your state) to use as a key in your memoization cache. For rob(['a', 'b', 'c']), the key might be "['a','b','c']". For calculate(10, 20), the key could be "[10,20]". This is a robust and flexible technique that works for a wide range of DP problems.

Conclusion

In this lesson, you've learned the first and most intuitive method for implementing Dynamic Programming solutions. By adding a simple caching layer to a recursive function, you can drastically improve its performance without fundamentally changing its logic.

Here are the key takeaways:

• Memoization is a top-down, recursive DP strategy that stores the results of subproblems in a cache to avoid re-computation.
• You can convert any brute-force recursive solution with overlapping subproblems into a memoized one by following a simple "check-compute-store" recipe.
• The cache is typically a hash map (Map or {} in JS/TS), mapping a representation of the state to its solution.
• When the state involves multiple arguments or non-primitive types, use JSON.stringify() to create a unique string key for the cache.

You now have a powerful tool to solve a large class of DP problems. The process is systematic: define the recursive structure, then apply the memoization recipe.

In our next lesson, we will explore the second major DP strategy: bottom-up tabulation. This approach solves the same problems without recursion by iteratively building up a table of solutions from the base cases. We'll compare it with memoization and see when you might prefer one over the other.