Минимум подпоследовательностей, необходимых для преобразования одной строки в другую

Question

Я пытался отработать алгоритм и наткнулся на этот вопрос: https://www.geeksforgeeks.org/minimum-number-of-subsequences-required-to-convert-one-string-to-another-using-greedy-algorithm/

Вероятно, похожий вопрос по stackoverflow: Найти минимальное число совпадений двух строк

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

Может ли кто-нибудь помочь мне разобраться в этом вопросе с помощью еще нескольких примеров? прежде чем я смогу попробовать написать алгоритм?

Answer 1

Я думаю, что основной причиной вашей проблемы может быть тот факт, что вы не знаете, как преобразовать строку B.
Итак, задача заявляет, что вы должны построить строку A из подпрограммы. последовательности B.

1. Все возможные подпоследовательности
   Пример строки B содержит 31 возможную подпоследовательность. Я не буду записывать их все.
   Просто чтобы получить суть, я буду использовать последовательность ABCD, который имеет только 16 возможных подпоследовательностей.

D
C
CD
B
BD
BC
BCD
A
AD
AC
ACD
AB
ABD
ABC
ABCD

Здесь в общих чертах объясняются подпоследовательности: https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

Строка сборки A
Теперь, после того, как вы нашли все возможные подпоследовательности, ваша задача собрать из них строку A.
Таким образом, вы должны добавить их для представления строки A .
Цель состоит в том, чтобы найти минимальное количество этих последовательностей, которое могло бы это сделать.
Так что, если последовательность сверху будет моей B, а A будет "ACDB", решение будет :

ACD + B => 2 sub sequences needed