Adding DP Caches

I'm posting this note because I noticed that a lot of people are having trouble implementing top-down DP caching in their functions. It's really nothing to be afraid of, and I hope that some code examples will help.

Whenever you have a recursive function, you should always think about whether it would benefit from caching. If you could ever have an overlapping sub-problem, you should probably implement caching.

Let's say you have a function that looks like this.

long recurse(int foo){
    long best;
    // perform some recursion, and save the best value in the variable "best"
    return best;

To add a cache, it takes just a few extra lines of code.

long recurse(int foo, Map<Integer,Long> cache){
        long best;
        // your main code here
        cache.put(foo, best);
    return cache.get(foo);

Then, when you first call your recursive function, just pass it a new instance of HashMap that you create.

System.out.println(recurse(100, new HashMap<Integer,Long>()));

If you need to identify your recursive case by more than one value, you can make a Pair.

import javafx.util.*; // at top of file.  This requires Java 8!

long recurse(int foo, int bar, Map<Pair<Integer,Integer>,Long> cache){
    Pair<Integer,Integer> key = new Pair<Integer,Integer>(foo, bar);
        long best;
        // your main code here
        cache.put(key, best);
    return cache.get(key);

Here is how you do the same things in Python.

# original function
def recurse(foo):
    # your code here
    return best

# cached function, one-variable key
def recurse(foo, cache):
    if foo not in cache:
        # your code here
        cache[foo] = best
    return cache[foo]

# cached function, two-variable key
def recurse(foo, bar, cache):
    key = (foo,bar)
    if key not in cache:
        # your code here
        cache[key] = best
    return cache[key]

# call your recursive function with a cache like this (the {} is an empty hash table)
recurse(100, {})