Memoization

Can make the recursive formulation work, as long as you don't let yourself compute the answer to the same question repeatedly.

• Create a hash table for each subroutine associating inputs to answers.
• No side effects, so same input means same output.
• Each time we compute an output, store it in the hash table.
• Before we try to compute a new answer, see if that one's already in the hash table (and return right away if it is).
• Get same worst-case bounds (often better best case).
• (Can do the same with DFS to identify ``reachable'' subproblems.)

Turn an exponential algorithm into a quadratic one!