[dahart]

Ah, you beat me to it. I came to make the same suggestion.

DP is fancy caching, but you have to think about the space of the solution to do it right. It's not just easier to cache the results and use the recursive solution, but the code is often smaller and clearer too.

I spent some time understanding and coding up edit distance between trees DP-style, which is a fair bit trickier than edit distance between strings. At the end of the whole project, I wished I had simply memoized.

[bitL]

Sometimes DP problems are pretty complex in a convoluted way employing some weird tricks before you could see it the DP way; it's best to take some advanced DP problems from TopCoder or ICPC and dissect them in detail. Trivial DP problems are phased out of interviews already, unless looking for junior positions.