[sanderjd]

I have always felt that dynamic programming is only confusing because of the name. The concept of caching previously calculated values in order to save time by avoiding recalculation (at the cost of using more space) is intuitive.

What am I missing?

[clickok]

Richard Bellman coined the name, and according to legend it was because the phrase 'dynamic programming' was so anodyne that not even the most officious bureaucrat could object.

In Bellman's own words[0]:

"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 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—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."

-----

0. From http://arcanesentiment.blogspot.com/2010/04/why-dynamic-prog...

[roryokane]

A link to the original paper that your source quotes: https://web.archive.org/web/20060209011347/http://www.eng.ta.... “Richard Bellman on the Birth of Dynamic Programming” by Stuart Dreyfus.

[sanderjd]

Thank you for this story :)

He clearly had no idea he'd be burdening generations of programmers preparing for interviews.

[eranation]

Not much. There is the top down and bottom up approach. Classic memoization (top down) needs the full past results to be cached. But sometimes you can save memory by doing it bottom up and only using the previous result of the smaller problem to get the larger problem.

In most interviews you should be good by just doing top down, which is more intuitive. But sometimes the bottom up approach will be the follow up question.

[akhilcacharya]

Formulating the recursion and caching strategy is the difficult part and it is non-trivial to identify at times.

For example, this is simple to explain in the abstract case but what about a concrete case like text justification or edit distance?

The hardest part is getting to the recurrence relation, and then implementing it.

[sanderjd]

Does the term only apply to recursive solutions? Caching is often useful in iterative solutions as well; does that count?

I would pretty much never start an interview response with a recursive solution in an interview because I pretty much never end up with a recursive solution in my work. I have very rarely been asked to do something recursively having already done it iteratively.

[akhilcacharya]

In a colloquial sense yes, DP includes both.

But to be precise, most people only consider the bottom-up approach to be actual Dynamic Programming.

[sgkzr]

Not really much. The only difference is that DP could have smaller cache size if calculation order is planned.

And I agree with you that it's only confusing because of the name.

[matz1]

I can relate, the name is so intimidating the first time I heard it.