Visualizing dynamic programming

"I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, 'Where did the name, dynamic programming, come from?' The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I'm not using the term lightly; I'm using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various rea- sons. I decided therefore to use the word, 'programming.' I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

So there you go: it was supposed to sound cool, and dynamic, and like something that any self-respecting congressman would want to fund. I'd always vaguely suspected.

Image seam carving. Remember when this was all the rage a while ago? The 2D offset pattern is "up-left, up, up-right" for the vanilla version of the algorithm. If you want to support seams with a sharper slope, the offset pattern will be correspondingly wider.

Optimal game playing. Whenever the space of states is much smaller than the space of move sequences, you probably want dynamic programming. Example: The game state consists of a string of tokens, each with a point value. Players take turns removing a token from the string's left or right edge, adding its value to their running score. Here the move space grows exponentially but the state space only grows quadratically.

Pseudo-polynomial algorithms for NP-complete problems. You can think of these as one-player games analogous to the above two-player games where as before the state space has small size compared to the move space. A classic example is the knapsack problem with integer weights and a small knapsack; here the table offsets would be the different weights.

I've long loved this quote from Steve Skiena:

"Once you understand it, dynamic programming is probably the easiest algorithm design technique to apply in practice. In fact, I find that dynamic programming algorithms are often easier to reinvent than to try to look up in a book. That said, until you understand dynamic programming, it seems like magic."

When I first read this as a kid having a hard time grokking dynamic programming, I thought it was bluster. Now I know it's the absolute truth. You could even argue that dynamic programming should be considered a single algorithm rather than an algorithm design technique, but that might be going too far.

In his diagrams, they indicate depends on. I think it would be more natural to draw them in the direction of the data flows - which cell each cell supports. That way the computation is visualized running in the direction of the arrows, rather than the reverse direction.

Found a post on how he makes them: http://blog.ezyang.com/2010/04/diagramming-in-xournal-and-gi... though if you have a tablet and a good sense of design the software is probably not that important.