Найдите самую короткую чередованную строку 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, уберите символ 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 (или обоих), которые вы сняли.

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

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