Dynamic programming is hard to learn and even harder to apply. We can make it easier with software.

# Fibonacci

1 | const fib = function(n) { |

# Let’s memoize it

1 | const memo = {}; |

It works! But now it’s harder to read.

# Let’s decouple memoization from the function with a closure

1 | Function.defaultHasher = function() { |

# Let’s memoize Fibonacci again

1 | let fib = function(n) { |

Awesome! We get readability *and* memoization. Any function that we write can now be memoized automatically! However, not all functions should be memoized.

# How do I know what to memoize?

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems.

…

Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems.

…

Overlapping sub-problems means that the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems.

…ok. If we can define our function in terms of its subproblems *and* the subproblems are often recomputed, then we know we can memoize. But how do we find that out?

We can go up to a whiteboard and start drawing a call tree. Or we can generate one!

# Let’s generate call trees with closures

1 | Function.defaultTracer = function() { |

Let’s see what this does:

1 | // 1. Define fib |

Beautiful! Although…that’s not something I would draw on a whiteboard. Maybe something more like this

I transformed the trace into a Graphviz source file then generated this image at Viz.js. I’ll leave the exercise up to you! (The source is a little too large to display here, but I’ll open source it soon).