Last week, while working through labs, I had a question for my partner. I was confused about what Dynamic Programming is.
I kept hearing the term while watching others work on algorithm challenges during our meetups.
I thought I had understood it before, but realized I didn't exactly.
This led to a long tangent on the history of the term Dynamic Programming and of course what it is.
Eye of the hurricane
Richard Ernest Bellman was an applied mathematician, who introduced dynamic programming in 1953. Bellman died on March 19th, 1984, but he left behind a wonderful autobiography that has a pretty funny excerpt pertaining to where the term Dynamic Programming came from.
Before I learned about this, my partner taught me that the 1950s were hostile to programming and research. Our government didn't view it as something worth investing in nor paying attention to. Bellman knew this and figured his way around this problem.
Here is an excerpt from Eye of the Hurricane.
“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 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” (p. 159)
He was correct that even a congressman couldn't reject this name.
I was under the impression that Dynamic Programming was something much more than it was. I was shown a simple to understand diagram and realized it wasn't something to be apprehensive of.
My understanding is you break down a problem into simpler, smaller problems. You store the solution to each sub-problem so that they are each only solved once.
The act of storing solutions to our sub-problems in dynamic programming is known as a technique called memoization.
For a better understanding of how to break a problem into sub-problems and go on to solve them, click here.
Thank you for reading!
Top comments (0)