我一直在下面的问题，从这个本书。

I have been working on the following problem from this book.

一个特定的字符串处理语言提供了一个基本的操作而将一个字符串转换成两块。由于这个操作涉及复制原始字符串，它需要的无论切口的位置n个单位的时间长度为n的串。假设，现在，你想打破字符串成许多碎片。其中，符所做的顺序可能会影响总的运行时间。例如，如果要削减20个字符的字符串在位置3和10，然后使头切3位招致20 + 17 = 37，总成本，同时做第一的位置10具有20+更好的成本10 = 30。

A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut at position 3 incurs a total cost of 20+17=37, while doing position 10 first has a better cost of 20+10=30.

我需要给米削减一个动态规划算法，发现切割字符串为m + 1个的最低成本。

I need a dynamic programming algorithm that given m cuts, finds the minimum cost of cutting a string into m+1 pieces.

推荐答案

分而治之的办法在我看来，最适合这类问题。下面是一个Java实现的算法：

The divide and conquer approach seems to me the best one for this kind of problem. Here is a Java implementation of the algorithm:

注意：数组 M 应该按升序进行排序（使用 Arrays.sort（M）; ）

Note: the array m should be sorted in ascending order (use Arrays.sort(m);)

public int findMinCutCost(int[] m, int n) {
   int cost = n * m.length;
   for (int i=0; i<m.length; i++) {
      cost = Math.min(findMinCutCostImpl(m, n, i), cost);
   }
   return cost;
}

private int findMinCutCostImpl(int[] m, int n, int i) {
   if (m.length == 1) return n;
   int cl = 0, cr = 0;
   if (i > 0) {
      cl = Integer.MAX_VALUE;
      int[] ml = Arrays.copyOfRange(m, 0, i);
      int nl = m[i];
      for (int j=0; j<ml.length; j++) {
         cl = Math.min(findMinCutCostImpl(ml, nl, j), cl);
      }
   }
   if (i < m.length - 1) {
      cr = Integer.MAX_VALUE;
      int[] mr = Arrays.copyOfRange(m, i + 1, m.length);
      int nr = n - m[i];
      for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[i];
      }
      for (int j=0; j<mr.length; j++) {
         cr = Math.min(findMinCutCostImpl(mr, nr, j), cr);
      }
   }
   return n + cl + cr;
}

例如：

 int n = 20;
 int[] m = new int[] { 10, 3 };

 System.out.println(findMinCutCost(m, n));

将打印 30

** 修改 **

我已经实现了两个其他的方法来回答这个问题的问题。

I have implemented two other methods to answer the problem in the question.

此方法切断总递归的最大块。结果并不总是最好的解决办法，而是提供了一个不容忽视的增益（+ 100000％的涨幅，从我的测试中的顺序），从最佳的成本可以忽略不计的最小割损的差异。

This method cut recursively always the biggest chunks. The results are not always the best solution, but offers a not negligible gain (in the order of +100000% gain from my tests) for a negligible minimal cut loss difference from the best cost.

public int findMinCutCost2(int[] m, int n) {
   if (m.length == 0) return 0;
   if (m.length == 1) return n;
      float half = n/2f;
      int bestIndex = 0;
      for (int i=1; i<m.length; i++) {
         if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
            bestIndex = i;
         }
      }
      int cl = 0, cr = 0;
      if (bestIndex > 0) {
         int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
         int nl = m[bestIndex];
         cl = findMinCutCost2(ml, nl);
      }
      if (bestIndex < m.length - 1) {
         int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
         int nr = n - m[bestIndex];
         for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[bestIndex];
      }
      cr = findMinCutCost2(mr, nr);
   }
   return n + cl + cr;
}

2。恒定的时间多切

计算的最小成本，只需要使用不同的指标和缓冲区。由于这种方法在一个恒定的时间执行时，它总是返回n。另外，该方法的实际上的分割字符串的子字符串。

2. A constant time multi-cut

Instead of calculating the minimal cost, just use different indices and buffers. Since this method executes in a constant time, it always returns n. Plus, the method actually split the string in substrings.

public int findMinCutCost3(int[] m, int n) {
   char[][] charArr = new char[m.length+1][];
   charArr[0] = new char[m[0]];
   for (int i=0, j=0, k=0; j<n; j++) {
      //charArr[i][k++] = string[j];   // string is the actual string to split
      if (i < m.length && j == m[i]) {
         if (++i >= m.length) {
            charArr[i] = new char[n - m[i-1]];
         } else {
            charArr[i] = new char[m[i] - m[i-1]];
         }
         k=0;
      }
   }
   return n;
}

注意：最后这个方法可以很容易地修改以接受一个字符串str 的说法，而不是 N ，并设置 N = str.length（），并返回从的String [] 阵列 charArr [] [] 。

Note: that this last method could easily be modified to accept a String str argument instead of n and set n = str.length(), and return a String[] array from charArr[][].