Dynamic Programming and the partition problem

The first thing to note about Dynamic Programming is that — you cannot memorize the patterns! Memoize, but do not memorize!

If you understand recursion — dynamic programming is just one and a half steps ahead of recursion. Always, Always, and I cannot emphasize it enough — ALWAYS come up with a recursive solution first!

The steps to approach a DP problem are :

• Write out the recurrence relation
• Write out code for the recursive solution (based on the recurrence relation)