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)