Алгоритм выравнивания текста

Question

Это очень известная проблема в DP. Может ли кто-нибудь помочь визуализировать ее рекурсивную часть? Как будут создаваться перестановки или комбинации.

ссылка на проблему. https://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

Answer 1

Учитывая максимальную ширину линии как L, идея, чтобы оправдать текст T, состоит в том, чтобы рассмотреть все суффиксы текста (рассмотрите слова вместо символов для формирования суффиксов, чтобы быть точным.) Динамическое программирование - не что иное, как "Осторожный грубый метод". Если вы рассматриваете метод грубой силы, вам нужно сделать следующее.

1. рассмотрите возможность размещения 1, 2, .. n слов в первой строке.
2. для каждого случая, описанного в случае 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 => на данный момент не осталось слов для записи.

Чтобы подвести итог:

1. Подзадачи: суффиксы, слова [:i]
2. Угадайте: с чего начать следующую строку, количество вариантов n - i -> O(n)
3. Повторение: 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();
    }
  }