Memoization: Top-Down Dynamic Programming

From Recursion to Memoization

A dynamic programming recurrence, like $F(n)=F(n-1)+F(n-2)$, naturally suggests a recursive function. However, as we've discussed, a naive recursive implementation often leads to exponential runtimes due to re-computing the same subproblems repeatedly.

Memoization is a technique that optimizes this process by caching the results of expensive function calls. When the function is called again with the same inputs, it returns the cached result instead of re-computing it. For DP, this means we solve each unique subproblem exactly once.

This process is a general optimization pattern:

1. Write a "brute-force" recursive function that directly implements the recurrence relation.
2. Add a cache (e.g., a hash map or an array) to store the results of subproblems.
3. In the recursive function, add a check at the beginning: if the solution for the current state is already in the cache, return it immediately.
4. If not, compute the solution as before, but store it in the cache before returning.

The following video from MIT OpenCourseWare introduces this concept using the familiar Fibonacci sequence. It provides a clear illustration of transforming a naive recursive algorithm into a fast, memoized one and establishes the fundamental model for analyzing its performance.

As the video explains, memoization ensures that the recursive body for each subproblem is executed only once. All subsequent calls for that same subproblem become constant-time lookups. This transforms an exponential-time exploration of a call tree into a linear-time traversal of the subproblem dependency DAG, where each node is visited just once.

Case Study: Coin Change

Let's apply this pattern to a more representative DP problem. The "Coin Change" problem asks if a target value V can be formed using a given set of coin denominations.

In the previous lesson, we would have modeled this as:

• State: possible(v), a boolean indicating if value v can be made.
• Recurrence: possible(v) = OR_{c in coins} possible(v-c) for all c <= v.
• Base Case: possible(0) = true.

Now, we will implement it. The following resource from Carnegie Mellon University provides an excellent, structured walkthrough.

The document also provides a clear cost analysis for the top-down solution, arriving at a runtime of $\Theta (V\cdot n)$, where $V$ is the target value and $n$ is the number of coin denominations. This aligns perfectly with the formula from the MIT video:

• Number of subproblems: $V+1$ (for values 0 to $V$).
• Work per subproblem: $O(n)$ (to iterate through the n coins).
• Total Time: $O(V\cdot n)$.

Memoization with Complex State: DP on Trees

The memoization pattern isn't limited to problems where the state is a simple integer index. It applies just as well to more complex states, such as nodes in a tree or tuples representing multiple parameters.

Recall the "Maximum Weight Independent Set on a Tree" problem from our last lesson (also known as "House Robber III"). We defined a refined state to solve it:

• f(u): the max weight of an independent set in the subtree at u, including node u.
• g(u): the max weight of an independent set in the subtree at u, excluding node u.

The recurrences were:
$f(u)=\text{weight}[u]+{\sum }_{v\in \text{children}(u)}g(v)$
$g(u)={\sum }_{v\in \text{children}(u)}\max (f(v),g(v))$

How do we implement the memoization cache for this? A simple array memo[i] is no longer sufficient if our nodes are objects in memory, not integers. This is a practical implementation detail that your background in runtime systems will appreciate. We need a way to map a subproblem (defined by a tree node u) to its solution (f(u) and g(u)).

The following article explores precisely this challenge.

The key insight is that the "memo" doesn't have to be an external data structure. By designing your recursive function to return the complete solution for a subproblem (e.g., a pair (f(u), g(u))), you implicitly pass the memoized values up the call stack. A parent u calls the function on its children v, receives the (f(v), g(v)) pair, and uses it to compute its own (f(u), g(u)) pair, which it then returns. The language's own function call stack manages the intermediate results, and if you use an explicit external cache (like a Map<TreeNode, SolutionPair>), you can prevent re-computation across disconnected parts of the call graph.

Summary

This lesson focused on translating a DP recurrence into a functional, efficient algorithm using top-down memoization.

• The Pattern: Memoized DP is essentially "clever recursion." You start with a simple recursive function and augment it with a cache to store subproblem solutions, avoiding redundant work.
• Direct Translation: This approach is a very direct translation of the mathematical recurrence into code, making it a natural first step when implementing a new DP solution.
• Complexity Analysis: The performance is easy to analyze with the formula: Time = (Number of States) × (Work per State), where the work per state excludes the cost of recursive calls.
• Implementation Matters: The choice of data structure for your memoization cache (array, hash map, or even the problem's own structure) is a practical consideration that depends on the nature of the state.

In our next lesson, we will explore the second major implementation strategy: bottom-up dynamic programming. Instead of starting from the top and recursively solving subproblems as needed, we will start with the base cases and iteratively compute the solutions to larger subproblems in a predetermined order—a process that directly corresponds to a topological sort of the subproblem DAG.