The interesting part of this problem for me is the OP's recurrence relation he comes up with at the end that makes the problem (trivially) soluble is the same s

The interesting part of this problem for me is the OP's recurrence relation he comes up with at the end that makes the problem (trivially) soluble is the same skill required to solve dynamic programming problems.