用于弦切割的动态编程练习

Question

我一直在研究本书中的以下问题.

某种字符串处理语言提供了一种原始操作,它将字符串分成两部分.由于此操作涉及复制原始字符串,因此无论剪切的位置如何,对于长度为n的字符串,都需要n个时间单位.现在假设您要将字符串分成许多部分.中断的顺序可能会影响总运行时间.例如,如果你想在3号和10号位置剪切一个20个字符的字符串,那么在第3个位置进行第一次剪切会产生20 + 17 = 37的总成本,而在第10个位置进行第一次剪切会产生更好的成本20+ 10 = 30.

我需要一个动态编程算法,给出m个切割,找到将字符串切割成m + 1个片段的最低成本.

Answer 1

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

注意：数组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

**编辑**

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

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

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

注意：最后一个方法可以很容易地修改为接受String str参数而不是nset n = str.length()，并返回一个String[]数组charArr[][]。