字符串切割的动态规划练习

我一直在研究以下问题book http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf.

某种字符串处理语言提供了将字符串分成两部分的原始操作。由于此操作涉及复制原始字符串，因此无论剪切位置如何，长度为 n 的字符串都需要 n 个单位的时间。现在假设您想将一根绳子分成许多部分。中断的顺序会影响总运行时间。例如，如果要在位置 3 和 10 处剪切 20 个字符的字符串，则在位置 3 处进行第一次剪切的总成本为 20+17=37，而首先进行位置 10 的成本则为 20+ 10=30。

我需要一个动态编程算法，给定 m 次切割，找到将字符串切割成 m+1 块的最小成本。

在我看来，分而治之的方法似乎是解决此类问题的最佳方法。下面是该算法的 Java 实现：

Note：数组m应按升序排序（使用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

** Edit **

我已经实现了另外两种方法来回答问题中的问题。

1. 中值割近似

这种方法总是递归地切割最大的块。结果并不总是最好的解决方案，但提供了不可忽略的增益（根据我的测试，增益约为 +100000%），与最佳成本的最小切损差异可以忽略不计。

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。另外，方法actually将字符串拆分为子字符串。

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;
}

Note：最后一个方法可以很容易地修改为接受String str论证而不是n并设置n = str.length()，并返回一个String[]数组来自charArr[][].