Your problem seems to be a pretty standard dynamic programming problem. I can explain the algorithm in more detail elsewhere or in person; LJ comments are certainly not the way.

I'll see if I can implement the versions without any restrictions and make it understandable, to boot. Or you can find me in person sometime.