Variant of rod cutting

Question

You are given a wooden stick of length X with m markings on it at arbitrary places (integral), and the markings suggest where the cuts are to be made accordingly. For chopping a L-length stick into two pieces, the carpenter charges L dollars (does not matter whether the two pieces are of equal length or not, i.e, the chopping cost is independent of where the chopping point is). Design a dynamic programming algorithm that calculates the minimum overall cost.

Couldn't figure out the recurrence. Was asked this in a recent programming interview.

Answer 1

With m marks, you have m+2 interesting points, 0 = left end-point, marks 1, ..., m, right end-point = (m+1).
Store the distance from interesting point 0 to interesting point i in an array to calculate costs.
Edit: (Doh, gratuitously introduced an unnecessary loop, noticed after seeing Per's answer again)
For each 0 <= l < r <= m+1, let cost[l][r] be the lowest cost for completely chopping the piece between points l and r. The solution is cost[0][m+1].

// Setup
int pos[m+2];
pos[0] = 0; pos[m+1] = X;
for(i = 1; i <= m; ++i){
    pos[i] = position of i-th mark;
}
int cost[m+2][m+2] = {0};
for(l = 0; l < m; ++l){
    // for pieces with only one mark, there's no choice, cost is length
    cost[l][l+2] = pos[l+2]-pos[l];
}
// Now the dp
for(d = 3; d <= m+1; ++d){  // for increasing numbers of marks between left and right
    for(l = 0; l <= m+1-d; ++l){ // for all pieces needing d-1 cuts
        // what would it cost if we first chop at the left most mark?
        best_found = cost[l+1][l+d];
        for(i = l+2; i < l+d; ++i){ // for all choices of first cut, ssee if it's cheaper
            if (cost[l][i] + cost[i][l+d] < best_found){
                best_found = cost[l][i] + cost[i][l+d];
            }
        }
        // add cost of first chop
        cost[l][i][l+d] = (pos[l+d] - pos[l]) + best_found;
    }
}
return cost[0][m+1];

Complexity: If you're naively checking all possible ways to chop, that'd make m! ways. Very bad. Taking into account that after any cut it doesn't matter whether you first completely chop the left part, then the right or interleave the chopping of the two parts, the complexity is (for m >= 2) reduced to 2*3^(m-2). Still very bad.
For our dp:

1. innermost loop, looping i; d-1 (l < i < l+d)
2. loop over l: m+2-d (0 <= l <= m+1-d), makes (m+2-d)*(d-1)
3. outermost loop, 3 <= d <= m+1, makes roughly m^3/6 steps.

Okay, O(m^3) isn't everybody's dream, but it's the best I could quickly come up with (after some inspiration from Per's post made me notice a prior inefficiency).