pllk in the Dynamic Programming chapter of his book describes a 3 step approach to DP problems:
- Find a recursive solution to the problem.
- Use memoization to improve the time complexity of this top-down recursive solution.
- Transform to a bottom-up iterative solution.
(Step 3 is practically optional since the time complexity should be the same as the memoized top-down recursive solution, but the constants will be better and the logic will often be more straightforward.)
pllk demonstrates this 3 step process with the Coin Change problem, and for this first example, the method works nicely.
However, the very next example is Longest Increasing Subsequence, in which it's not at all obvious how to complete the first step of writing a recursive solution.
So the 3 step method above works for many problems in which you can actually take the first step and identify the recursive solution. In fact it seems like the critical, most important and difficult step: if you can get past step 1, steps 2 and 3 are rarely a problem.
But what do you do when step 1 isn't obvious, and you get stuck not being able to make progress with this method?
In fact, I almost never use these steps.