Разбираем задачку с LeetCode на Dynamic Programming⁠⁠

Вчера у меня случилась великая радость - я наконец-то без подсказок написал решение medium DP задачи, используя bottom-up подход (то есть циклом вместо рекурсии). Рекурсивные (up-down) подходы более интуитивны, зато циклы дают лучшую производительность и меньшее потребление памяти. В общем, давайте попробуем разобрать daily-challenge c LeetCode за вчерашний день.

Начинаем с интуитивного решения. Рекурсивно переберем все возможные варианты.

Предсказуемо работает - и вылетает по Time Limit. Еще бы, у нас Time Complexity O(n^3). Кошмар.

Но ведь это задачка на DP. Даже если бы этого не было в тегах - все равно можно понять, что места для оптимизации тут есть, ведь мы по факту обрабатываем некоторые подстроки по многу раз. Скажем, если мы возьмем слово длиной в 5 символом, то, построив стек вызовов в виде обычного бинарного дерева, можно убедиться, что подстрока [2,3] будет проверена трижды. Не круто.

Давайте-ка добавим мемоизацию.

О, мы сразу прошли все тесты (снизили TC до O(n^2)). Но результаты не радуют.

Плохо. В основном плохо из-за мемоизации строк (приходится тратить время и место на их обрезку и хранение), плюс недешевая проверка на палиндром в O(n). Давайте-ка перепишем на bottom-up.

Мы помним, что у задачек на палиндром есть три общих случая в зависимости от длины строки n:

• Если n = 1, строка всегда палиндром (в каком направлении букву не читай, выйдет одно и то же).

• Если n = 2, то строка палиндром, если первая буква равна последней.

• Если n > 2, то строка считается палиндромом, если первая буква равна последней, и строка между ними - палиндром.

Собственно, мы просто заполняем dp таблицу прямо по этому принципу.

Смотрите, какая красота

Да, это все еще в нижней планке решений (благодаря тому, что существует довольно замысловатый алгоритм, решающий эту проблему за линейное время), но в три раза сократили Runtime, и в два - потребление памяти. Это все еще O(n^2), но скажем так, с куда более приемлимыми константами.

Собственно, это был, наверное, один из наиболее базовых алгоритмов на тему динамического программирования, и шансы, что что-то подобное спросят на собеседовании в FAANG, довольно высоки. Просто посмотрите на топик Companies.

Так что имеет смысл уметь решать dp алгоритмы и сверху вниз, и снизу вверу. Чисто на всякий)