Найти кратчайшую чередующуюся строку A и B с динамическим программированием

Question

У меня возникла проблема с вопросом о динамическом программировании.

Для двух строк A и B найдите кратчайшую чередующуюся строку из двух.

Например, для A = "APPLE", B = "ABSOLUTE"

Самый короткий ответ будет "ABPPSOLUTE" Вместо ответа моя функция возвращает "APPABSOLUTE"

Моя идея, чтобы решить эту проблему, было чередовать A [0] и B [0] постоянно len(A)+len(B) раз Но это не сработало.

Answer 1

Вот некоторые идеи, которые помогут вам начать работу.

Тега вика для динамического программирования описывает его как:

Динамического программирование является алгоритмическим методом для эффективного решения задач с рекурсивной структурой, содержащего множество перекрывающихся подзадач

Так первым, попробуйте и думать способа рекурсивного решения проблемы. Спросите: «Как я могу откусить небольшую часть этой проблемы и обработать ее таким образом, чтобы то, что я оставил, является еще одним примером проблемы»?

В этом случае «маленькая деталь» будет единственным символом, а оставшиеся символы в строке будут оставлены. Подумайте о проблеме как о том, «каково кратчайшее чередование символов этих двух строк, начиная с позиции X строки A и позиции Y строки B»? Когда вы вызываете его на начальном этапе, X и Y равны 0.

три варианта ответа на этот вопрос являются:

• Если X не в конце, возьмите символ A [X] выкл строка A , затем решим проблему рекурсивно для X + 1, Y (найдите кратчайшее чередование двух строк, начинающихся с X + 1, Y)
• Как указано выше, но взяв символ из строки B вместо A и рекурсивного решения для X , Y + 1
• В том случае, когда символы A [X] и B [Y] идентичны, выведите символ из обоих и найдите решение для X + 1, Y + 1

Если X и Y достигли конца A и B, верните пустую строку.

Верните кратчайшую строку из вышеуказанных 3, добавленную к символу из A или B (или обоих), которые вы сняли.

Когда функция возвращается с верхнего уровня, у вас должен быть ваш ответ.

Это «рекурсивная» часть. «Перекрывающиеся подзадачи» - это то, как вы повторно используете материал, который вы уже рассчитали. В этом случае вы можете сделать 2-мерный массив строк, который представляет проблему, решаемую для всех возможных значений X и Y, и при входе в функцию проверьте, есть ли у вас ответ и просто верните его, если вы это сделаете. Если нет, то выполните его, как указано выше, и перед возвратом из функции сохраните значение, которое вы собираетесь возвращать в массиве в местоположении [X] [Y].