Учитывая максимальную ширину линии как L, идея, чтобы оправдать текст T, состоит в том, чтобы рассмотреть все суффиксы текста (рассмотрите слова вместо символов для формирования суффиксов, чтобы быть точным.)
Динамическое программирование - это не что иное, как «осторожная грубая сила».
Если вы рассматриваете метод грубой силы, вам нужно сделать следующее.
- рассмотрите возможность размещения 1, 2, .. n слов в первой строке.
- для каждого случая, описанного в случае 1 (скажем, слова i помещаются в строку 1), рассмотрите случаи помещения слов 1, 2, .. n -i во вторую строку, а затем оставшихся слов в третью строку и так далее. .
Вместо этого давайте просто рассмотрим проблему, чтобы выяснить стоимость размещения слова в начале строки.
В общем случае мы можем определить DP (i) как стоимость для рассмотрения (i-1) -го слова как начала строки.
Как мы можем сформировать рекуррентное отношение для DP (i)?
Если j-е слово является началом следующей строки, то текущая строка будет содержать слова [i: j) (исключая j), а стоимость j-го слова, являющегося началом следующей строки, будет DP (j).
Следовательно, DP (i) = DP (j) + стоимость помещения слов [i: j) в текущей строке
Поскольку мы хотим минимизировать общую стоимость, DP (i) можно определить следующим образом.
Отношение повторения:
DP (i) = min {DP (j) + стоимость размещения слов [i: j в текущей строке}
для всех j в [i + 1, n]
Примечание j = n означает, что в следующей строке не осталось слов для вставки.
Базовый регистр: DP (n) = 0 => на данный момент не осталось слов для записи.
Подведем итог:
- Подзадачи: суффиксы, слова [: i]
- Угадай: с чего начать следующую строку, # вариантов n - i -> O (n)
- Повторение: DP (i) = min {DP (j) + стоимость помещения слов [i: j) в текущую строку}
Если мы используем мемоизацию, выражение внутри фигурной скобки должно занимать O (1) раз, а цикл запускается O (n) раз (число вариантов выбора).
i Варьируется от n до 0 => Следовательно, общая сложность снижается до O (n ^ 2).
Теперь, даже несмотря на то, что мы вывели минимальную стоимость для обоснования текста, нам также необходимо решить исходную проблему, отслеживая значение j для выбранного в качестве минимального значения в вышеприведенном выражении, чтобы впоследствии мы могли использовать его для печати из обоснованного текста. Идея заключается в сохранении родительского указателя.
Надеюсь, это поможет вам понять решение. Ниже приведена простая реализация вышеуказанной идеи.
public class TextJustify {
class IntPair {
//The cost or badness
final int x;
//The index of word at the beginning of a line
final int y;
IntPair(int x, int y) {this.x=x;this.y=y;}
}
public List<String> fullJustify(String[] words, int L) {
IntPair[] memo = new IntPair[words.length + 1];
//Base case
memo[words.length] = new IntPair(0, 0);
for(int i = words.length - 1; i >= 0; i--) {
int score = Integer.MAX_VALUE;
int nextLineIndex = i + 1;
for(int j = i + 1; j <= words.length; j++) {
int badness = calcBadness(words, i, j, L);
if(badness < 0 || badness == Integer.MAX_VALUE) break;
int currScore = badness + memo[j].x;
if(currScore < 0 || currScore == Integer.MAX_VALUE) break;
if(score > currScore) {
score = currScore;
nextLineIndex = j;
}
}
memo[i] = new IntPair(score, nextLineIndex);
}
List<String> result = new ArrayList<>();
int i = 0;
while(i < words.length) {
String line = getLine(words, i, memo[i].y);
result.add(line);
i = memo[i].y;
}
return result;
}
private int calcBadness(String[] words, int start, int end, int width) {
int length = 0;
for(int i = start; i < end; i++) {
length += words[i].length();
if(length > width) return Integer.MAX_VALUE;
length++;
}
length--;
int temp = width - length;
return temp * temp;
}
private String getLine(String[] words, int start, int end) {
StringBuilder sb = new StringBuilder();
for(int i = start; i < end - 1; i++) {
sb.append(words[i] + " ");
}
sb.append(words[end - 1]);
return sb.toString();
}
}