棒材切割的变种

Question

你会得到一根长度为X的木棒，上面有m个标记，在任意位置(整数)，这些标记表示要在哪里进行相应的切割。对于将一根L长度的木棒切成两段，木匠收取L美元的费用(这两段长度是否相等并不重要，也就是说，切割成本与切断点的位置无关)。设计一种计算最小总成本的动态规划算法。

不能计算出重复性。在最近的一次编程采访中被问到了这个问题。

Answer 1

有了m个标记，你就有了m+2感兴趣的点，0=左端点，1，...，m，右端点= (m+1)。

将兴趣点0到兴趣点i的距离存储在数组中，以计算成本。

编辑： (Doh，无缘无故地引入了一个不必要的循环，再次看到Per的答案后注意到了)

对于每个0 <= l < r <= m+1，假设cost[l][r]是在点l和r之间完全切分的最低成本。解决方案是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];

复杂性:如果你天真地检查了所有可能的切分方法，那就是m！方式。非常糟糕。考虑到在任何切割之后，无论您是先完全切割左侧部分，然后是右侧部分，还是交错地切割这两个部分，复杂度(对于m >= 2)被降低为2*3^(m-2)。还是很糟糕。

对于我们的dp：

最里面的循环，在l上循环i；d-1 (l

• 循环: m+2-d (0 <= l <= m+1-d)，makes (m+2-d)*(d-1)

• outermost loop，3 <= d <= m+1，大约m^3/6步。

好吧，O(m^3)并不是每个人的梦想，但它是我能很快想到的最好的(从Per的帖子中得到的一些灵感让我注意到了之前的低效)。

Answer 2

对于每一对(标记|端点)，计算出切割杆段的最便宜的方法。对于每个分段，最小化该分段中的第一个裁剪的选择。

Answer 3

我猜你是想让木匠切割一次，然后继续切割，直到所有的棍子都被切割，而你是在询问切割的顺序？

在这种情况下，一种方法是通过可能组合的树进行深度优先递归搜索，在树中计算成本，记录第一个序列及其成本，然后从这一点开始，避免下降到成本较高的树中，并始终记录找到的任何较便宜的序列。