evening. Are you willing to monitor this thread and walk through this? (Given that it's a homework problem) I'll try to give hints as we go.
Most dynamic programming problems can be described recursively, often as a search, where computations of that recursive search are duplicated. So often I try to work it from defining a recursive solution, the 'hard search', and go from there.
Let's say that L describes a log that is to be broken up into segments L1, L2, .. Ln. The cost for cutting log L is fixed, because length(L) is known. But where I cut affects what the costs of future cuts are. Also, the order of L1, L2, L3.... Ln may not be in an optimal order. Although cutting the current log L is fixed, if the order of the sublengths is changed, then future costs may be affected.
Given this, how would you do this recursively? (As a hard search I mean) (ie break the large problem down into smaller problems?)
|
