Dynamic programming exercise for string cutting

algorithm, dynamic-programming

Solution

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

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

For example :

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

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

Will print `30`

** Edit **

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

1. Median cut approximation

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

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[][]`.

Problem

Original source