So I realize, you know this is a little abstract at the moment.
We've only have one concrete example to relate to these abstract concepts.
I encourage you to revisit this again after we see more examples and we will
see many more examples. Something that all of the forthcoming
examples should make clear is the power and flexibility of a dynamic programming
paradigm. This is really just a technique that you
have got to know. Now when you're trying to devise your own
dynamic programming algorithms, the key, the heart of the matter is to figure out
what the right sub problems are. If you nail the sub problems usually
everything else falls into place in a fairly formulaic way.
Now if you've got a black belt in dynamic programming you might be able to just
stare at a problem. And intuitively know what the right
collection of subproblems are. And then, boom, you're off to the races.
But, of course, you know? For white belts in dynamic programming,
there's still a lot of training to be done.
So rather, in the forthcoming examples. Rather than just plucking the subproblems
from the sky. We're going to go through the same kind
of process that we did for independent sets.
And try to figure out how you would ever come up with these subproblems in the
first place? By reasoning about the structure of
optimal solutions. That's a process you should be able to
mimic in your own attempts at applying this paradigm to problems that come up in
your own projects. So, perhaps you were hoping that once you
saw the ingredients of dynamic programming, all would become clearer why
on earth it's called dynamic programming and probably it's not.
So, this is an anachronistic use of the word
programming. It doesn't mean coding in the way I'm
sure almost all of you think of it. It's the same anachronism in phrases like
mathematical or linear programming. It more refers to a planning process, but
you know for the full story let's go ahead and turn to Richard Bellman
himself. He's more or less the inventor of dynamic
programming, you will see his Bellman-Ford Algorithm a little bit later
in the course. So he answers this question in his
autobiography and he's says, he talks about when he invented it in the 1950's
and he says those were not good years for mathematical research.
He was working at a place called Rand, he says we had a very interesting gentleman
in Washington named Wilson who was the 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 we felt then about
the term mathematical. So 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 and decision making, but planning, it's not a good word for
various reasons. I decided therefore to use the word,
Programming. Dynamic has a very interesting property
as an adjective, in that it's poss, 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.
