1-D Dynamic Programming

The result for each state is stored in a list, and each new result is computed from the results before it.