棒切割的变种

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：

1. 最内层循环，循环i；d-1（l < i < l+d）
2. 循环 l: m+2-d (0 <= l <= m+1-d)，使得 (m+2-d)*(d-1)
3. 最外面的循环，3 <= d <= m+1，大约进行 m^3/6 步。

好吧，O(m^3) 不是每个人的梦想，但它是我能很快想出的最好的（在 Per 的帖子的一些启发让我注意到之前的低效率之后）。