Где применяется
1. Задача
Все уроки про DP до этого заполняли таблицу простым проходом. Одномерная таблица (шаг 111) росла слева направо. Сетка (шаг 113) заполнялась строка за строкой. Рюкзак (шаг 114) и наибольшая возрастающая подпоследовательность (шаг 115) читали только клетки, которые этот проход уже записал раньше. Поэтому обычного порядка «строка за строкой, слева направо» везде хватало. В этом уроке клетка зависит от более короткого отрезка внутри себя, и порядок заполнения придётся сменить.
Вот задача. Подпоследовательность это то, что остаётся после удаления части символов без перестановки остальных: "ace" это подпоследовательность "abcde". Палиндром читается одинаково слева направо и справа налево. longestPalindromeSubseq(s) возвращает длину самой длинной подпоследовательности s, которая читается как палиндром. Для "bbbab" ответ 4 ("bbbb"). Для "cbbd" ответ 2 ("bb"). Для "abcde" ответ 1, потому что ни одна буква не повторяется.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на палиндромы в подстроках и подпоследовательностях. Клетка от i до j берётся из более коротких отрезков внутри неё, так что заполняй таблицу по длине отрезка, от 2 до n.
Задача урока слово в слово.
Отмечай клетку от i до j как true, когда крайние буквы равны и середина палиндром, и посчитай клетки true.
Та же таблица true или false, где ты запоминаешь самый длинный отрезок с true. n не больше 1000, так что n^2 клеток проходят.
Каждой букве вне самой длинной палиндромной подпоследовательности нужна пара, так что ответ это n минус результат урока.