Is there a canonical book on dynamic programming?

Question

At the moment in college I'm studying dynamic programming and I'm really interested in it. I want to go deeper and fully understand the topic so I can write good dynamic code.

Is there a book out there that's the de-facto standard for describing best practices, design methodologies, and other helpful information about dynamic programming? What about that book makes it special?

Answer 1

When I first started on the Dynamic programming technique - it was almost like trying to digest recursion. Finally This is the current representation I have in mind:

1. note the lowest forms of the problem.
2. Usually, the future computations are either the same as one of the best old values or an incremental update. Build a formula for this.
3. Repeatedly increase the constraint space in both dimensions until you get to the value you are looking for.

Now - with an example: 0-1 knapsack problem. Consider bag capacity of C and N items of various values v0 to vN and corresponding sizes s0 to sN. Start with actual values instead of notations like above. So your bag size would be 50 and items denoted as id(size, value) would be 1(10, 20), 2(15, 30), 3(5,15), 4(50,1000).

1. Have a 2 dimensional table with C on rows and N on columns.
2. Start with a bag capacity of 1 (C=1).
3. See what is the best fit for this. (There might be no items with a size of 1 as given here). Fill in the first row.
4. Now keep increasing the bag size. At one point (when you reach the row C=5), you will be able to fit the smallest item (id=3). This will continue to be the best until the bag size grows to the second biggest element (when you reach the row C=10).
5. Now you will have a choice. Either you could continue with the old item / have the new item - based on their values. choose the best. (In this case, choose id 1)
6. continue on. Soon you will get to a value of C where you can choose a combination of items. (When C=15 here. now you can either have 1,3 items or just item 2. here the choice is based on the whether the value of 1 and 3 is higher than value of item 2. (here value of 1 & 3 is higher. 35 > 30).
7. As you move like this, you will see a pattern. Instead of trying to find the best for the current location as an independent entity, you can base it off the values in your table itself. This is the solution given at http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem.

Inductive reasoning helps a lot in this algo technique - Hope I helped :)

Answer 2

To start from the beginning, check out MIT's lecture videos for introduction to algorithms on their OpenCourseWare site

As you watch these, first learn and understand recursion. Then try to really understand what's going on and what the algorithm is doing.

Answer 3

If your after a book on dynamic programming for .NET 4, have a look at this one. I can't rate it as i only briefly thumbed through it in a book store.

Pro Dynamic .NET 4.0 Applications