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)
• Try to cache(using a HashMap or any other data structure you prefer) the repetitive function calls —this is known as top-down dynamic programming
• Rack your brain to come up with a bottom-up DP approach. (Preferrably using a 2D-array)
• Try to push yourself a little further to use a 1D array instead of a 2D array for the bottom-up solution
• Ignore the previous step- if you’re losing interest :D

So, I picked up this problem from Jeff Erickson’s book on Algorithms : (http://algorithms.wtf) [Please check out his book. It is hands-down the best book on algorithms!]

Given an array A[1 .. n] of characters, compute the number of partitions of A into words. For example, given the string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL.