Quote:Is there a dynamic programming approach to this problem?

The answer is rather simple, Dynamic Programming is an optimization, it is about avoiding doing same calculations again and again.

So the method is rather simple :

1) Build a solution for the problem, as simple as possible.

2) Make sure problem is solve, if not refine your solution until it works.

3) Analyze how your program solves the problem, if you spot that your code is recalculating the same thing again and again, then dynamic programming can apply.