При рекурсивном подходе к этой проблеме 25-й/1307-й тестовые случаи потребовали тайм-аута. По большей части рекурсия медленнее и занимает больше стека вызовов. Возьмем, к примеру, строку 9. Это вызов lcs для двух частей (i+1, j) и (i, j+1). После первых двух итераций становится ясно, что эта функция вызвала lcs для тех же значений i и j. Повторный вызов одной и той же функции и параметра не приводит к оптимизации и увеличивает стек вызовов до такой степени, что мы достигаем тайм-аута.
Этот второй метод использует мемоизацию — метод, используемый для ускорения программ путем сохранения результатов ранее вызванной функции. Мемоизация предотвращает необходимость повторного запуска функции и позволяет получить доступ к данным внутри сохраненного объекта. Тем не менее, мемоизация меняет преимущества памяти за счет скорости. Благодаря экономии места функция смогла пройти большинство тестов.
Наконец, в этой функции очевидны преимущества использования динамического программирования. Динамическое программирование — это способ решения сложных проблем путем разбиения их на более мелкие подзадачи. В случае lcs, где цель состоит в том, чтобы найти самую длинную общую подстроку, выходные данные представлены матрицей n+1 и m+1 (n — длина первого входа, m — длина второго входа). DP сохраняет значения ранее запущенных функций в матрицу и объединяет предыдущие решения для получения наиболее оптимального решения.
