What is Dynamic Programming?

Dynamic programming has nothing to do with computer programming; the name was coined in the 1940's by the American mathematician Richard Bellman in the 1940's back when "programming" did not refer to the business of writing computer code. Basically, DP was developed as a tool for finding the best path for an activity. The definition of "best" depended on context. Most of what I know about the subject comes from Mathematical Optimization and Economic Theory by Michael D. Intriligator (1971, Prentice-Hall).

Some of you will want to brush past me; here are three online resources on DP:

1. "Dynamic Programming," David B. Wagner (courtesy Wikipedia)
2. "A Tutorial on Dynamic Programming," Michael A. Trick (courtesy Wikipedia)
3. Lecture Notes on Optimization, Pravin Varaiya, Chapter 9 (1971; 1998; PDF; courtesy Alex Stef).
   

Prof. Varaiya's link is a math book, so be advised; it's in PDF and very well-done. The part about DP is on PDF-129 and following.

In the meantime, I'll be discussing a few concepts as I skim them in this textbook on my lap.

First, a note on the word "programming": this is a mathematical term initially applied to the problem of choosing values of certain variables so as to maximize or minimize a given function, relative to constraints. For example, suppose you can enclose a yard with a fence of finite length. The area is a*b, but the fence cannot be longer than 2a+2b=C. This is a pretty basic problem in calculus. You can use much more complex versions of this problem to find the optimal shape of a part used in a machine, or the optimal path of a rocket being launched into space.

(To be continued)