Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
1  
It seems maybe the two concepts are conflated. "Good dynamic code" sounds more like programming style in a dynamic language. But the phrase "dynamic programming" should refer to the algorithmic technique. –  Macneil Oct 30 '10 at 19:24
    
As long as you write clean, readable, simple code, your technique will develop quickly. Good dynamic code follows "write your code only once" very strictly. Sometimes this can lead to readability and management problems. Also make sure you comment why you are doing something and not how, how should be described by the code itself. –  Scott Oct 31 '10 at 6:17
    
If you're into videos - youtube.com/watch?v=6h6Fi6AQiRM –  irrelephant Oct 31 '10 at 8:49
    
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 –  GrumpyMonkey Oct 31 '10 at 10:38
add comment

1 Answer

up vote 3 down vote accepted

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 :)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.