Help with a dynamic programming solution to a pipe cutting problem
For me, it makes more sense to think about this problem in reverse.  The problem is posed as a destructive process - you have 1 pipe, and you split it into many.  However, in terms of the cost calculation, the reverse process results in the same answer.  That is, if you take the resulting pipe segments and start gluing them back together, using the sum of the length of the two pieces you're gluing as the cost of the operation, you end up with the same cost.  

So then the question becomes the following:

given a set of pipe segments, what is the cheapest order of gluing segments together until you  have only one segment?  This assumes a cost function where c(x1,x2) = len(x1) + len(x2).

This is trivial when you have two segments.  There's only one way to glue them together, so that has to be the cheapest way.  

With three segments, it starts to be a bit more interesting.  

Lets say we have lengths x1, x2, and x3.  We have three options for our first operation:
x1 + x2, x2 + x3, and x1 + x3.  No matter what values are in x1, x2, and x3, the operation after this one will cost the same.  That is to say the following:

(x1 + x2) + x3 == (x2 + x3) + x1 == (x1 + x3) + x2

As a result, the cheapest way of putting the three pieces of pipe back together is going to be the way that has the cheapest first step.  

Then the question becomes, which of the first steps is the cheapest?

That depends on what the values in x1, x2, and x3 are.  Lets assume the three values are in ascending order.  So x1 &lt;= x2 &lt;= x3.  Now you can determine which starting pair is the cheapest, right?  Its the pair containing the smallest values, or x1 and x2.  Note that there is the possibility that two or more of the three values are the same.  I'll leave it up to you to convince yourself that such a scenario is not a problem.  

So we've got a solution for either 2 or 3 pieces.  This should give you some insight towards a general solution.