What do i need to know about dynamic programming?

Question

Started up solving UVa problems again as a way to pass time (going to the army in 6 weeks). I love writing Java, but end up using C / C++. It's not because IO is faster, no need to box data, more memory or use of unsigned, because its algorithm efficiency that counts.

In short i am slowly constructing how to/article/code base for different categories of efficient algorithms and dp is next.

Quoting Mark Twain: It ain't what you don't know that gets you into trouble. It's what you know for sure that just ain't so.

I aid assistance in building priority list what are must have efficient algorithms.

Answer 1

This MIT lecture is a good introduction to dynamic programming if you're already familiar with algorithms.

Answer 2

The wikipedia article on Dynamic Programming has a section entitled "Algorithms that use dynamic programming" with many examples.

Here is another good list of practice problems in dynamic programming.

Since you referenced the UVa problem list, you should definitely take a look at Problem 103 - Stacking Boxes. The problem lends itself well to a solution using a Longest Increasing Subsequence algorithm.