Hm. Actually, I might have misunderstood the problem. I'm still sure there is a fairly simple solution to it - it's probably more of a graph theory problem (but, of course, the standard algorithms use DP to speed things up). I'll think about it some more.