Разбираем задачку с 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)). Но результаты не радуют.
Особенно ужасает потребление памяти. Даже для Java это перебор.
Плохо. В основном плохо из-за мемоизации строк (приходится тратить время и место на их обрезку и хранение), плюс недешевая проверка на палиндром в O(n). Давайте-ка перепишем на bottom-up.
Мы помним, что у задачек на палиндром есть три общих случая в зависимости от длины строки n:
Если n = 1, строка всегда палиндром (в каком направлении букву не читай, выйдет одно и то же).
Если n = 2, то строка палиндром, если первая буква равна последней.
Если n > 2, то строка считается палиндромом, если первая буква равна последней, и строка между ними - палиндром.
Собственно, мы просто заполняем dp таблицу прямо по этому принципу.
Гораздо симпатичнее, но в разы менее интуитивно
Смотрите, какая красота
Да, это все еще в нижней планке решений (благодаря тому, что существует довольно замысловатый алгоритм, решающий эту проблему за линейное время), но в три раза сократили Runtime, и в два - потребление памяти. Это все еще O(n^2), но скажем так, с куда более приемлимыми константами.
Собственно, это был, наверное, один из наиболее базовых алгоритмов на тему динамического программирования, и шансы, что что-то подобное спросят на собеседовании в FAANG, довольно высоки. Просто посмотрите на топик Companies.
Так что имеет смысл уметь решать dp алгоритмы и сверху вниз, и снизу вверу. Чисто на всякий)
Лига программистов
2.3K поста12K подписчиков
Правила сообщества
- Будьте взаимовежливы, аргументируйте критику
- Приветствуются любые посты по тематике программирования
- Если ваш пост содержит ссылки на внешние ресурсы - он должен быть самодостаточным. Вариации на тему "далее читайте в моей телеге" будут удаляться из сообщества