What are systematic ways to prepare for dynamic programming?

Answer by Michal Danilák:

I don't know how far are you in the learning process, so you can just skip the items you've already done:

  1. Read the Dynamic programming chapter from Introduction to Algorithms by Cormen and others. You have to understand the theory of dividing a problem into subproblems, storing the intermediate results in the array and see how are some standard problems solved with DP.
  2. Read my tutorial on Are there any good resources or tutorials for dynamic programming besides the TopCoder tutorial?. It teaches you how to come up with memoization solution for the problems, which is much easier than standard DP solution with iteration. I strongly advice you to use this technique.
  3. Solve problems! Dynamic programming is something you learn by practice. There is no magic formula, no shortcut. But remember, "practice good, not hard". I have posted some good sources in the thread Where can I find good problems to practice recursion/topdown approach?. Always try to choose a little harder problem than you're comfortable with and solve it. Don't bother with easy problems. It gives you nothing besides the typing speed.

There are more types of dynamic programming problems. Here are the most famous ones, sorted increasing by their difficulty:

  1. Problems which simply ask you to come up with the formula of calculating the answer from the subproblems. These are the most common ones and probably the ones you want to practice on (95+% of DP problems are of this type). On TopCoder, they are usually ranked as Div1-500 and easier. On other online judges just look for the problems with many successfull solutions.
    The number of dimensions of the array doesn't really tell much about the problem difficulty, so don't judge based on that. It only needs a little more implementation.
    The hardest problems in this category require you to use bitmasks. For example:
    http://community.topcoder.com/stat?c=problem_statement&pm=11379&rd=14437&rm=308640&cr=22685656
    Here is a very nice tutorial on bit manipulation techniques:
    http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation
  2. Problems which require you to come up with efficient linear recurrence, putting the recurrence into the matrix and calculate the N-th power of the matrix. Examples are:
    http://www.spoj.pl/problems/XORROUND/
    http://www.spoj.pl/problems/TRKNIGHT/
    http://www.spoj.pl/problems/RP/
  3. Problems which require you to eliminate the inner cycle in the algorithm. For more information you can look at Knuth's speedup of calculating the optimal binary search tree (http://dl.acm.org/citation.cfm?id=1644032) or:
    http://community.topcoder.com/tc?module=HSProblemStatement&pm=8712&rd=12046
  4. Problems which require you to effectively calculate and operate on the convex hull of the optimal solutions. For a nice problem with a solution, look at the problem Harbingers from CEOI 2009. Other examples are:
    http://www.spoj.pl/problems/MKPAIRS/
    http://www.spoj.pl/problems/NKLEAVES/
    http://www.spoj.pl/OI/problems/CEOI09HA/

That's pretty much all you need to know. A word of advice: don't think about it too much. Just solve the problems (not the easy ones!) and after some time your brain will start to recognize the patterns. You will be faster and able to solve harder problems and suddenly you'll become an expert 😉

What are systematic ways to prepare for dynamic programming?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s