Memoization & dynamic programming
Memoization
A way to trade space for time and make recursion more efficient.
The basic idea
If our recursive function is pure (i.e. its value depends only on the values of its immutable arguments) we don’t need to recompute values if we’ve computed them before.
So the first time we compute our function for a particular set of arguments, we remember (memoize) the value so we don’t have to compute it again later.
Memoized functions keep the basic recursive structure but cache answers once they are computed.
A simple, general approach
Make a Map to store already computed values with the arguments as the key.
Each time the function is called, check the map to see if the value for that particular set of arguments has already been computed.
If it hasn’t compute it and add it to the map.
Return the value from the map, either the one that was already there or the one we just added.
Memoized fibonacci
private static Map<Integer, Long> memo = new HashMap<>();
public static long fibonacci(int n) {
if (n < 2) {
return n;
} else {
if (!memo.containsKey(n)) {
memo.put(n, fibonacci(n - 1) + fibonacci(n - 2));
}
return memo.get(n);
}
}Naive recursive fibonacci
Memoized recursive fibonacci
Making a key
When there’s only one argument, it can be the key.
But if you are memoizing a function with multiple arguments, you need to combine them into a single key.
Records are great for this.
As long as the arguments are all unchanging values with a good equals and hashCode methods, a record containing those args will work as a key.
Using a record key
private record Key(int n) {}
private static Map<Key, Long> memo = new HashMap<>();
public static long fibonacci(int n) {
if (n < 2) {
return n;
} else {
Key k = new Key(n);
if (!memo.containsKey(k)) {
memo.put(k, fibonacci(n - 1) + fibonacci(n - 2));
}
return memo.get(k);
}
}Some choices
Do you make a single map that lives forever, which can be used whenever the function is called?
Or do you define the actual computation in terms of a helper function that takes the map as an argument and then define the actual function to create a new map and then call the helper?
What are the trade-offs?
Temporary memo table
public static long fibonacci(int n) {
return memoFib(n, new HashMap<>(Map.of(0, 0L, 1, 1L)));
}
public static long memoFib(int n, Map<Integer, Long> memo) {
if (!memo.containsKey(n)) {
memo.put(n, memoFib(n - 1, memo) + memoFib(n - 2, memo));
}
return memo.get(n);
}Make sure in your helper method you recurse using the helper method, not the top-level method.
Less general approach
Sometimes there’s a lighter weight data structure to use for memoization.
Array memoized fibonacci
public static long fibonacci(int n) {
return memoFib(n, new long[n + 1]);
}
private static long memoFib(int n, long[] memo) {
if (n < 2) {
return n;
} else {
if (memo[n] == 0) {
memo[n] = memoFib(n - 1, memo) + memoFib(n - 2, memo);
}
return memo[n];
}
}Limitations of memoization
Memoization is usually pretty easy to bolt on to an existing recursive solution. But it doesn’t solve all the problems with recursion.
In particular since memoization still relies on recursion it still requires a call stack as deep as the path from the starting problem to the base cases so it doesn’t help with StackOverflowExceptions.
Dynamic programming
Dynamic programming is a way of restructuring recursive solutions into an iterative form.
It flips things around by starting at the base case(s) and putting them into a table.
Then it computes up from the base cases, computing the next values from previously computed values.
Note, this term doesn’t come from computer science so neither “dynamic” nor “programming” mean what we’re used to.
Two requirements
-
Overlapping sub-problems
-
Optimal substructure
Overlapping sub-problems
A problem has overlapping sub-problems if the same sub-problems (i.e. the problems we solve with recursive calls) are solved over and over again in a naive recursive solution.
For instance computing the nth Fibonacci number with the naive recursive solution computes fib(n - 2) twice, once directly and once under the fib(n - 1) tree.
Non-overlapping sub-problems
Note, not all recursive solutions have overlapping sub-problems. Tree searches, such as binary search, typically do not because you only have to process each sub-tree once.
Optimal substructure
A problem has optimal substructure if we can combine the optimal answer to a sub-problem with any of the ways we could have arrived at that sub-problem to get an answer to the larger problem.
If that’s true, then to find the optimal answer to the original problem we just need to find the path to the sub-problem that, combined with the optimal answer to the sub-problem gives us the best global answer.
🤓 Actually 🤓
Technically there are other substructures that also work with dynamic programming such as Additive and Logical.
Even more technically, any algebraic structure that forms a Semiring works.
Dynamic programming fibonacci
public static long fibonacci(int n) {
if (n < 2) {
return n;
}
var table = new long[n + 1];
table[1] = 1;
for (int i = 2; i < table.length; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[n];
}Optimizing space usage
Once we’ve organized our computation this way, sometimes we can then see that we don’t actually need to keep all the old answers.
In fibonacci, each new entry only needs the two before it: once we’ve computed fib(i) and fib(i + 1) we’ll never need to look back at fib(i - 1) again.
So we don’t actually need a whole table, just two variables, and we can run in constant space.
Fibonacci with two variables
public static long fibonacci(int n) {
if (n < 2) {
return n;
}
long prev = 0;
long curr = 1;
for (int i = 2; i <= n; i++) {
long next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}This is someting you might have come up with on your own.
Fibonacci with a rolling table
public static long fibonacci(int n) {
var table = new long[] { 0, 1, 0 };
for (int i = 2; i <= n; i++) {
table[i % 3] = table[(i - 1) % 3] + table[(i - 2) % 3];
}
return table[n % 3];
}This is basically the same as the two-variable version just with a single three-element array rather than separate variables.
Using % on the indexes allows the actual indexes to cycle around the array.