[zestyping]

Is dynamic programming the same as memoized recursion, or does it include techniques beyond that?

[gowld]

Consider Fibonacci. Memoized recursion uses O(n) memory, because you don't garbage-collect anything. Bottom-up dynamic programming is O(1) memory, because you only need to remember the largest 2 subvalues you've computed.

[ufo]

Pretty much. Although sometimes it is more natural to build up the solution "bottom up" instead of using memoization.

The tricky bit is figuring out what is the recurrence relation (recursion) for the problem you are trying to solve.

[sn41]

It is basically memoized recursion. However, that does not mean that it is easy. To find out the optimal substructure - that is, building the solution to the problem from the optimal solution of its subproblem decomposition - is where the actual difficulty of the technique lies.

Exercises from a standard algorithm textbook like Kleinberg and Tardos should give enough practice in solving these problems. Not all of them are straightforward.