algorithm - 切割一根棍子，以使成本最小化

你必须把一根长度l的棍子切成几块。必须在c1, c2, c3, ..., cn位置进行切割，其中ci是1和n-1之间的整数（包括）。切割的成本等于它所用木棍的长度。削减的顺序应该是什么，以使整个行动的成本降到最低？
例如，考虑一根长度10的棍子，必须在2, 4, 7位置进行切割。你可以按所给的顺序切树枝。第一次切割成本10，因为木棒的长度10第二次切割将花费8，因为切割所用的剩余木棒长度10 - 2 = 8。最后一次切割将花费6，因为剩余的木棒长度10 - 4 = 6。总成本10 + 8 + 6 = 24
但是，如果我们按以下顺序切割木棒：4, 2, 7，我们将得到10 + 4 + 6 = 20的成本，这对我们更有利。
设计一个算法来解决这个问题。
我很确定这是一个dp问题。我能看到的一个诱人的重复关系是，如果我们切一根棍子，我们会得到两个更小的棍子。如果我们知道这两个棍子的最优解，我们就可以很容易地找出较大棍子的最优解但这将是非常低效的。
如果有一个递归函数min_cost(stick_length, c_1, c_2, ..., c_n)返回在stick_length处切割一根长度为c_1, c_2, ..., c_n的棍子的最小成本，则递归关系如下所示

min_cost(stick_length, c_1, c_2, ..., c_n) =
    stick_length
    + minimum(min_cost(c_1, a_1, a_2, ..., a_i)
    + min_cost (stick_length - c_1,
                a_(i+1), ..., a_(n-1)),
                min_cost(c_2, a_1, a_2, ..., a_i)
    + min_cost(stick_length - c_2,
               a_(i+1), ..., a_(n-1)), ... ,
               min_cost(c_n, a_1, a_2, ..., a_i)
    + min_cost(stick_length - c_n,
                a_(i+1), ..., a_(n-1)))`,

其中a_1, a_2, ..., a_n是要切割的剩余位置的排列。我们必须把所有可能的排列传递给递归函数，而不是像我写的那样只传递一个。
这显然不切实际。我该怎么解决？

最佳答案

另一个DP解决方案：
成本（a，b）是在a-th和b-th切点之间切割线段的最佳成本。很明显，成本（a，a）和成本（a，a+1）是零。我们可以计算出成本的最佳值（a，b），即通过所有中间点a+1…b-1加上自身段长度的最小切口。因此，我们可以用对角线填充三角形表对角线，并用O（n ^ 3）时间复杂度和O（n ^ 2）空间求最终结果作为代价（开始，结束）。
Delphi代码（输出Cost 20 Sequence 4 2 7）

var
  Cuts: TArray<Integer>;
  Cost: array of array of Integer;
  CutSequence: array of array of String;
  N, row, col, leftpos, rightpos, cutpos, Sum: Integer;
begin
  Cuts := TArray<Integer>.Create(0, 2, 4, 7, 10); // start, cuts, end points
  N := Length(Cuts);
  SetLength(Cost, N, N);  //zero-initialized 2D array
  SetLength(CutSequence, N, N);  //zero-initialized 2D array

  for rightpos := 2 to N - 1 do
    for leftpos := rightpos - 2 downto 0 do begin //walk along the diagonals
                                                  //using previously computed results
      //find the best (mincost) cut
      Cost[leftpos, rightpos] := MaxInt; //big value
      for cutpos := leftpos + 1 to rightpos - 1 do begin
        Sum := Cost[leftpos, cutpos] + Cost[cutpos, rightpos];
        if Sum < Cost[leftpos, rightpos] then begin
          Cost[leftpos, rightpos] := Sum;
          //write down best sequence
          CutSequence[leftpos, rightpos] := Format('%d %s %s', [Cuts[CutPos],
            CutSequence[leftpos, cutpos], CutSequence[cutpos, rightpos]]);
        end;
      end;

      //add own length
      Cost[leftpos, rightpos] :=
        Cost[leftpos, rightpos] + Cuts[rightpos] - Cuts[leftpos];
    end;

  //show the best result
  Caption := Format('Cost %d  Sequence %s',[Cost[0, N-1], CutSequence[0, N-1]]);

关于algorithm - 切割一根棍子，以使成本最小化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53522953/