Рекурсия к динамическому программированию

Пошаговый подход к решению любой задачи динамического программирования

Существует множество статей, объясняющих концепции динамического программирования и способы решения проблемы с использованием подходов динамического программирования сверху вниз и снизу вверх. Если вы еще не читали, я предлагаю вам прочитать мою статью, в которой рассматриваются основы Динамического программирования.

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

Поиск рекурсивного отношения - вот что дает решение для динамического программирования. В этой статье мы собираемся взять пример проблемы из LeetCode под названием Самая длинная общая подпоследовательность, а затем решить ее с помощью рекурсии, затем подхода сверху вниз (мемоизация), а затем преобразовать ее в метод снизу вверх. Подход.

Постановка задачи:

Given two strings str1 and str2, return the length of their longest common subsequence.
Input: str1 = "abcde", str2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Рекурсивное решение:

Есть два важных элемента проблемы рекурсии:

1. Поиск базового случая
2. Нахождение отношения повторяемости

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

if m == 0 or n == 0:
return 0;

Рекуррентное соотношение найти просто. Если значения m и n равны, мы добавляем единицу и находим самую длинную общую подпоследовательность остальной части строки.

if str1[m-1] == str2[n-1]:
return 1 + lcs(str1, str2, m-1, n-1);
else:
return max(lcs(str1, str2, m, n-1), lcs(str1, str2, m-1, n))

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

Подход сверху вниз (мемоизация):

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

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

В приведенном выше решении результат сохраняется в двумерной таблице под названием L.

Подход «снизу вверх:

В подходе снизу вверх мы используем итеративный подход для решения проблемы динамического программирования снизу. Мы начинаем с инициализации базовых случаев в таблице и используем ранее вычисленные результаты для продвижения вперед.

Создайте двухмерную таблицу с длиной строк в виде строк и столбцов.

L = [[None]*(n+1) for i in range(m+1)]

Используйте два цикла for, и подход аналогичен рекурсии, когда у нас есть два условия, когда оба символа похожи, а когда нет.

Анализ сложности времени:

1. Рекурсивное решение: рекурсивное решение в худшем случае имеет экспоненциальную временную сложность O (2 ^ N).
2. Подход сверху вниз (мемоизация): подход сверху вниз решает проблему за время O (mn), где m - длина строки 1, а n - длина строки 2.
3. Подход снизу вверх: он требует двух циклов и, следовательно, имеет временную сложность O (mn), аналогичную подходу сверху вниз.

Подходы сверху вниз и снизу вверх имеют одинаковую временную сложность, но поскольку подход сверху вниз реализован с использованием рекурсии, существует вероятность переполнения стека из-за чрезмерного количества рекурсивных вызовов.

Спасибо, что дочитали статью до конца, надеюсь, она поможет вам в подготовке к написанию кода. Подпишитесь на меня, чтобы увидеть больше таких статей.

Ресурсы: