The pretty printing problem - EPI

The pretty printing problem

Pretty_printing.cpp PrettyPrinting.java
  public static int findPrettyPrinting(List<String> W, int L) {
    // Calculates M(i).
    long[] M = new long[W.size()];
    Arrays.fill(M, Long.MAX_VALUE);
    for (int i = 0; i < W.size(); ++i) {
      int bLen = L - W.get(i).length();
      M[i] = Math.min((i - 1 < 0 ? 0 : M[i - 1]) + (1 << bLen), M[i]);
      for (int j = i - 1; j >= 0; --j) {
        bLen -= (W.get(j).length() + 1);
        if (bLen < 0) {
          break;
        }
        M[i] = Math.min((j - 1 < 0 ? 0 : M[j - 1]) + (1 << bLen), M[i]);
      }
    }

    // Finds the minimum cost without considering the last line.
    long minMess = (W.size() >= 2 ? M[W.size() - 2] : 0);
    int bLen = L - W.get(W.size() - 1).length();
    for (int i = W.size() - 2; i >= 0; --i) {
      bLen -= (W.get(i).length() + 1);
      if (bLen < 0) {
        return (int) minMess;
      }
      minMess = Math.min(minMess, (i - 1 < 0 ? 0 : M[i - 1]));
    }
    return (int) minMess;
  }