As many authors note, DP is an approach, not an algorithm. At a high level (so high as to be almost useless), dynamic programming (DP) can be viewed in two different ways:

• Taking a recursive top-down solution and caching (memoizing) the intermediate shared results for efficiency
• Solving a big problem by building a table of best solutions to simpler problems, incrementally, bottom-up.

The first view is helpful when you have a recursive but exponential solution, e.g., the standard recursive function for calculating Fibonacci numbers, and you want to create a more efficient solution.

Weiss discusses several examples of DP in Chapter 10, Section 10.3, but never actually defines what DP is.

Here are some readable online resources that describe DP solutions to various problems. I deliberately avoided the more mathematical sites:

• What is Dynamic Programming (PDF) by Sean R. Eddy -- a gentle introduction to DP for biologists, using the DNA alignment example.
• Dumitru's TopCoder tutorial on dynamic programming -- another brief introduction, using the example of making change
• The Wikipedia entry on Dynamic Programming -- introduces the important required property of optimal substructure
• Jesse's Introduction to Dynamic Programming -- similar to the Wikipedia entry; includes the maximal subsequence sum problem, which our textbook introduced in chapter 1 of Weiss
• Chapter 6 from Kleinberg and Tardos' Algorithm Design -- an excellent extended discussion. We use this book as a text sometimes. It's a better introduction to algorithmic analysis but weak on programming.
• Chapter 15 from Chinneck's Practical Optimization (PDF) -- notes that Dijsktra's cheapest path algorithm is DP, and gives a nice study of the equipment replacement problem and the classic knapsack problem
• Moshe Sniedovich's Dijkstra's Algorithm Revisited -- an extended look at Dijsktra's algorithm from a DP optimization point of view

Comments? Send mail to c-riesbeck@northwestern.edu.