Создать сообщение из персонажей журнала вырезки (вопрос интервью)

Question

Эта проблема возникает из главы о динамическом программировании в Руководство по разработке алгоритма by Skiena.

Дайте алгоритм, чтобы определить, можно ли генерировать данную строку, вставляя вырезиз журнала.Вам предоставляется функция, которая идентифицирует символ и его положение на обратной стороне страницы для любой заданной позиции символа.

Я решил это с помощью обратного отслеживания, но так как это в главе динамического программированияЯ думаю, что должно быть повторение, которое я не могу понять.Кто-нибудь может дать мне подсказку?

Answer 1

Вы можете решить это с максимальным двойным соответствием.

Каждый символ L данной строки образует левый набор. (Обратите внимание, вы повторяете символы, если строка содержит повторяющиеся символы).

Каждая пара символов (R1, R2) журнала образует правильный набор.

L подключен к (r1, r2), если L = R1 или L = R2.

Найти максимальное совпадение в результирующем графике. Если все левые вершины являются частью соответствия, у вас есть ответ. Если нет, такая строка невозможна.

См. Максимальное двойное соответствие для алгоритма.

Не уверен, что это оптимально, и извините за то, что не отвечаете точно так, как просили.

Answer 2

Если у вас есть рекурсивное решение для возврата, вы можете применить памятка , что является одним из способов динамического программирования.