Top-Down (Memoization)
Overview
There are two distinct ways to implement Dynamic Programming: Top-Down and Bottom-Up.
Top-Down (Memoization) starts at the massive, complex final goal (e.g., fib(40)) and writes standard, elegant recursion to break it down. The only difference between pure recursion and Memoization is the addition of a cache (usually an array or HashMap).
Before doing any recursive work, the method checks if (cache.contains(n)) return cache.get(n). If the answer isn't in the cache, it calculates it recursively, and rigorously saves it to the cache before returning.
Memoization is incredibly intuitive for developers because you write the algorithm exactly as you would normally think about standard recursion. However, because it still fundamentally relies on recursion, it suffers from JVM Call Stack overhead and can still trigger StackOverflowErrors for extremely deep trees.
Syntax
public class Memoization {
public int climbStairs(int n) {
// Cache array initialized with zeros
int[] memo = new int[n + 1];
return helper(n, memo);
}
private int helper(int n, int[] memo) {
// Base cases
if (n <= 2) return n;
// MEMOIZATION CHECK: If we already calculated this, return it instantly
if (memo[n] != 0) {
return memo[n];
}
// Otherwise, calculate it via heavy recursion
int result = helper(n - 1, memo) + helper(n - 2, memo);
// SAVE to cache before returning so we never do this work again
memo[n] = result;
return result;
}
}Common Pitfalls
- StackOverflowError on very deep inputs. Because it relies on the call stack,
climbStairs(100000)will crash your program in Java, even with memoization. - Forgetting to save the result. If you calculate the result but return it without assigning it to
memo[n], your cache remains empty and your algorithm remains O(2^N). - Using HashMaps unnecessarily. If your state is an integer from 0 to N, an
int[]array is vastly faster and uses less memory than aHashMap<Integer, Integer>.
Interview Questions
Yes, top-down recursion is essentially performing a Depth-First Search on the state-space tree of the problem. You dive deep to the base cases first before rolling back up.
When not all subproblems need to be solved. Memoization computes only the states that are strictly required to reach the answer. Tabulation blindly computes every single state from 0 to N, which can be wasteful if the problem space is sparse.
Real-World Example
Quick-to-write optimizations during tight deadlines. If a production system is suddenly crashing due to a highly complex recursive function (like a combinatorial pricing engine), an engineer can wrap it in a HashMap (Memoization) in exactly 3 lines of code to fix the outage instantly, rather than spending hours redesigning it iteratively.
public class LegacySystem {
private Map<String, Double> quickCache = new ConcurrentHashMap<>();
// Wrapped legacy recursion with an instant memoization fix
public double heavyCalculation(String inputState) {
if (quickCache.containsKey(inputState)) return quickCache.get(inputState);
double result = performLegacyRecursion(inputState);
quickCache.put(inputState, result);
return result;
}
}Check Your Knowledge
Test your understanding of Top-Down (Memoization) with these quick questions.