Где применяется
1. Задача
Ты сравниваешь две версии файла и хочешь, чтобы diff показал, что осталось прежним. Строки добавляли, удаляли, переставляли. Неизменная часть это самый длинный набор строк, которые есть в обоих файлах в одном и том же порядке, даже если между ними вставлены другие строки. Именно это git diff считает каждый день.
Похожая задача. Тебе дали номера сборок в случайном порядке. Нужно найти самую длинную цепочку обновлений, которую можно применить по этому списку и ни разу не откатиться к более старой сборке.
У обоих вопросов одна форма: выбери самое длинное, что можно сохранить по порядку. Элементы между выбранными разрешено пропускать.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитlongestIncreasingSubsequence([2, 5, 3, 7, 4, 8])Ищем самую длинную возрастающую подпоследовательность. Каждый dp[i] начинается с 1: само arr[i] уже цепочка длины 1.
Столбики: исходные числа, их никто не переставляет. Подсвечено число, которое сейчас читается; при выборе подмножества подсвечены все его элементы.
Одна операция: одно чтение элемента или выбор следующего подмножества. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(2ⁿ·n)O(n²)O(n log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- самая длинная возрастающая подпоследовательность
- самая длинная общая подпоследовательность двух строк
- минимум правок, чтобы превратить одну строку в другую
- сохранить относительный порядок, можно пропускать элементы
- diff или выравнивание двух последовательностей
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Там хватает одного индекса. Сравнению двух последовательностей нужны два.
- DP на строках (word break) (DP on strings (word break))
Та страница режет одну строку на куски. Эта выравнивает две последовательности.
- Бинарный поиск (массив) (Binary search (array))
Версия возрастающей подпоследовательности за n log n использует бинарный поиск. Табличная версия медленнее.
- Два указателя (в одну сторону) (Two pointers (same direction))
Проверке, является ли строка подпоследовательностью, таблица не нужна. Поиску наибольшей общей нужна.
Одна последовательность из n элементов стоит O(n²) времени. Две длины n и m стоят O(nm), и хватает одной строки памяти.
На LeetCode
Задачи, где элементы выбирают по порядку с пропусками так, чтобы каждый следующий рос, делился или сцеплялся с предыдущим. Для каждой позиции храни лучший ответ, который на ней кончается, проверяя все позиции раньше, это O(n^2).
Это lengthOfLIS из урока. n не больше 2500, так что таблица за O(n^2) проходит.
Рядом с каждой длиной храни, сколько выборов её дают, и складывай счётчики, когда две ранние позиции дают одинаковую длину.
Сначала отсортируй числа, потом запусти цикл урока, где вместо «меньше» стоит «делится», и храни ссылку на предыдущий элемент, чтобы восстановить набор.
Посчитай таблицу роста слева и ещё раз справа. Лучшая вершина горы оставляет больше всего элементов, и у неё должен быть хотя бы один элемент с каждой стороны.