Richard Bellman on the Birth of Dynamic Programming (2002) [pdf]

Several problems this year were DP already. This year is much easier than 2023, but Day 21 was hard.

A common misconception by design [1]. The research that was "hidden" behind this innocent-sounding name is very closely tied to the origins of backpropagation in the work of Paul Werbos where it will be further developed as "approximate dynamic programming." Bellman's research is more general and is close to a lot of thinking in physics after Lagrange, indeed quite close to the very notion of a "Lagrangian." Over-simplifying, the question has to do with optimization and guarantees of convergence inside various increasingly less-deterministic processes: how can we provably find true maxima of a given function step-by-step.

[1] In the article, an extract from Bellman's very interesting biography, we read:

"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... 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 reasons. 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... 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 com- bination 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.”

Here's an early intro from Bellman himself: https://www.ams.org/journals/bull/1954-60-06/S0002-9904-1954...

It gets into continuous problems from section 6 on.

That is how it is implemented, but the core idea is that a lot of problems can be broken down into subproblems that require shared, repetitive computations to solve, and the table is a way to cache/share those results for each subproblem.

The name "dynamic programming" has never clicked for me. I've looked it up I think multiple times over the years, and I think oh "recursive" or all the code I've written in Lisp/Elm. The distinction seems relatively "meh" to me.