The iterative version of the algorithm works by directly computing the entries in M rather than relying on the memoized recursion present in the recursive version. This algorithm works by iterating though the n items and computing each ones value, which is then stored directly in the array. It is easy to see that the algorithm then has linear running time since it will execute a constant time operation on each of its n passes through the loop.
From here we are able to develop an outline of dynamic programming. There are three properties that should be true of a problem in order to guide or development of a dynamic programming approach to solving the problem. First, there must be only a polynomial number of subproblems. Additionally, the solution to the original problem should be easy to arrive at from the solutions to the subproblems. Finally, there should be an ordering to the subproblems which allows the solution of some subproblems to be computed from the solutions of other subproblems.
Sometimes, it can be a challenge to determine whether it is more useful to first reason about the structure of the optimal solution or whether it is more useful to come up with subproblems that seem natural and then figuring a recurrence which links them. In this way, dynamic programming can be reminiscent of a chicken-and-the egg reasoning puzzle.