Заставка
00:00:00Дорожная карта динамического программирования с двумя параметрами Сосредоточьтесь на динамическом программировании с двумя индексами. Начните с задач, в которых оба параметра имеют одинаковую природу (grid-подобный DP сродни 1D), затем переходите к задачам, в которых параметры различаются, и, наконец, рассмотрите вариант, основанный на подстроках. Одна и та же дисциплина определения состояний, повторений, оснований, порядка и размещения ответов лежит в основе всех частей.
Основные принципы DP, лежащие в основе каждого решения Точно определите, что хранит каждая ячейка DP. Выразите целевое количество с помощью связей с меньшими подзадачами, возможно, введя удобные вспомогательные состояния. Подготовьте базовые значения, выберите порядок вычислений, который учитывает зависимости, и узнайте, какая ячейка содержит окончательный ответ.
Максимизация траектории черепахи по сетке Черепаха движется только вправо или вниз по прямоугольной сетке, собирая монеты; жадный выбор не удался, потому что локальные максимумы могут перекрыть путь. Храните в каждой ячейке максимальное количество монет, которое можно получить, войдя в нее. Перейдите от верхнего или левого соседа, возьмите максимальное значение и добавьте монеты текущей ячейки, чтобы получить значение.
Инициализация нейтрального элемента и размещение ответа Добавьте фальшивые 0-ю строку и столбец и инициализируйте их нейтральным элементом, чтобы крайние ячейки не нуждались в особых случаях. Для максимизации без отрицательных значений используйте 0; для минимизации используйте +бесконечность; для максимизации с возможными отрицательными значениями используйте −бесконечность. Окончательный ответ находится в правой нижней ячейке, куда направляется черепаха.
Шаблоны смещения соседей для сеточных алгоритмов Представьте соседние направления с помощью массивов небольших смещений и повторяйте их, чтобы равномерно посещать соседние ячейки. Расширьте шаблон до четырех- или восьмиугольных сеток, диагоналей или даже гексагональных сеток, регулируя смещения. Этот метод упрощает как переходы DP, так и общую логику обхода сетки.
Негативные ячейки создают конкурирующие цели Если посещение камеры может стоить денег, черепаха должна избегать потерь. Теперь важны две величины: текущие денежные средства и самый большой долг, с которым она столкнулась на своем пути. Оптимизация только одного из них вводит в заблуждение, потому что путь, который на короткое время достигает -100, а затем набирает +1000, может быть лучше пути с небольшими долгами, но небольшой прибылью; будущее неизвестно на момент принятия решения.
Переформулировка решения и бинарный поиск по стартовым деньгам Задайте начальную величину X и спросите, сможет ли черепаха достичь цели без того, чтобы баланс не опустился ниже нуля. Запустите привычный DP, но запретите переходы в ячейки, которые могут привести к отрицательному балансу. Выполнимость в X монотонна: если X работает, то работает любой X большего размера; если X не работает, то не работает любой X меньшего размера. Бинарный поиск минимального X, который делает DP выполнимым.
Ограниченность и сложность решения с учетом долговых обязательств Время выполнения каждого из этапов проверки выполнимости пропорционально площади сетки. Диапазон двоичного поиска ограничен значением от 0 до длины пути (N+M−1), умноженной на максимальную стоимость ячейки. Общая сложность - это площадь сетки, умноженная на логарифмический коэффициент в этой границе.
Самая длинная общая подпоследовательность через префикс DP Самая длинная общая подпоследовательность получается путем удаления символов из обеих строк. Пусть DP[i][j] - это длина LCS для первых i символов первой строки и первых j символов второй. Если текущие символы совпадают, возьмите диагональ плюс единицу; в противном случае возьмите максимальное количество верхних и левых ячеек.
Восстановление LCS без дополнительной памяти Восстановите LCS, пройдя от конца таблицы в обратном направлении. Когда текущее значение будет равно либо верхнему, либо левому соседу; связи позволяют использовать любой путь и дают разные, но оптимальные ответы. Перемещайтесь по диагонали и добавляйте символ только в том случае, если символы совпадают и значение диагонали ровно на единицу меньше.
Измените расстояние с помощью функций вставки, удаления и замены Допустимы три операции с удельными затратами: вставка, удаление и замена. Если символы совпадают, сохраните предыдущую стоимость; в противном случае выберите минимальную из следующих значений: замена (по диагонали+1), удаление (вверх+1) и вставка (влево+1). Эта формулировка напоминает настройку LCS и может быть обобщена до неединичных, даже вещественных значений, весов операций, когда вероятность возникновения некоторых ошибок более высока.
Нюансы практической значимости и производительности Дистанция редактирования лежит в основе таких функций, как коррекция поисковых запросов и создание предложений. Поиск расстояний методом перебора по всему словарю выполняется слишком медленно. В реальных системах эта идея сочетается с более сложными алгоритмами масштабирования.
Базовые варианты для LCS и редактирования расстояния Введите дополнительную верхнюю строку и левый столбец для представления пустых префиксов. Для LCS любое состояние, содержащее пустую строку, имеет значение 0, поэтому добавленные строка и столбец равны нулю. Для изменения расстояния преобразование пустого значения в пустое стоит 0, и эти базовые записи определяют согласованные начальные точки для повторения.
Порядок оценки и удобный обход кэша Пройдитесь по таблице, чтобы при необходимости были готовы все зависимости. Выполните итерацию с помощью внешнего цикла по строкам и внутреннего цикла по столбцам в текущей строке, чтобы использовать типичные схемы расположения памяти. Этот порядок часто является самым быстрым в распространенных языках программирования и представлениях 2D-массивов.
Почему прямое двухпараметрическое определение стоимости денег и долга терпит неудачу Пространство состояний, которое отслеживает для каждой ячейки как текущие денежные средства, так и самый большой долг, комбинаторно увеличивается. Возможные суммы могут достигать длины пути, умноженной на максимальную стоимость каждой ячейки, что значительно увеличивает размер сетки. Такая таблица является неразрешимой, поэтому необходим подход "решение плюс бинарный поиск".
Купоны в течение нескольких дней: определение состояния При N известных ежедневных ценах, заплатив более 100 долларов, вы получаете купон, который можно обменять на бесплатное питание в любой день. Цель состоит в том, чтобы свести к минимуму общие расходы и, используя столь же дешевые стратегии, максимально увеличить количество сохраняемых купонов. Определите DP[i][k] как минимальную сумму денег, потраченную после приема пищи в течение первого дня и заканчивающуюся ровно k купонами.
Скидки на купоны меняются в зависимости от цены и действия Воспользуйтесь купоном сегодня: купите в первый день с k+ 1 купонами и сохраните прежнюю стоимость. Оплатите, когда сегодняшняя цена превысит 100: купите в первый день с k−1 купонами и добавьте сегодняшнюю цену (и вы получите купон). Оплатите, когда сегодняшняя цена будет меньше 100: начните с первого дня с k купонов и добавьте сегодняшнюю цену. Использование купона в день скидок разрешено, но не дает права на новый купон.
Базовое состояние и порядок итераций в Day–Coupon DP Начните с 0-го дня с 0 купонов стоимостью 0, а все остальные состояния отметьте как недостижимые с бесконечностью, потому что цель состоит в том, чтобы минимизировать затраты. Большее количество купонов в 0-й день невозможно, поэтому они остаются бесконечными. Порядок обхода имеет значение: выполнение итераций по строкам без использования кэширования (после замены осей, если необходимо) ускоряет работу программы в несколько раз. Переориентируйте дни и купоны таким образом, чтобы динамика отображалась по строкам, а не по неудобным столбцам.
Почему Одномерный DP не работает для получения обеденных купонов Будущее неизвестно: обеды могут стать очень дорогими или очень дешевыми, что сделает купоны либо важными, либо бесполезными. Оптимизация только для минимальной общей стоимости или только для максимального количества купонов лишает возможности использовать их в будущем. Оба параметра должны учитываться во всех штатах. Один скалярный DP не может надежно зафиксировать этот компромисс.
Покупка кирпича по розничным и оптовым ценам Каждый магазин продает кирпичи по розничной цене до определенного порогового значения, затем переходит на оптовую цену за кирпич. Оптовый сегмент формирует новую линейную ветвь, и как только запасы в магазине превышаются, стоимость становится бесконечной. Возможны нелогичные случаи: оптовая цена может быть даже выше розничной. Общая стоимость каждого магазина представляет собой кусочно-линейную функцию с конечным бесконечным концом, когда запасы заканчиваются.
Функция учета затрат в одном магазине как основа DP Определите функцию, которая для данного магазина и желаемого количества соответствующим образом выбирает розничную или оптовую цену и умножает ее на количество. Если запрашиваемое количество превышает запас, возвращает значение infinity. Эта функция линейна до и после порогового значения, а затем переходит в бесконечность за пределами запаса. Используйте его для заполнения базовой строки, когда доступно только одно хранилище.
Объединение Хранилищ С Помощью Переходов между Состояниями Настройте DP на количество первых рассматриваемых магазинов и общее количество необходимых кирпичей. Для k магазинов и j кирпичей попробуйте купить x кирпичей (0..j) в k-м магазине, а остальные − в первых k-1 магазинах, взяв минимальное количество. В примере с двумя магазинами, состоящем из двух блоков, естественно, перечисляются варианты 0+2, 1+1 и 2+0. Если новый магазин является чрезмерно дорогим, DP просто копирует значения из предыдущей строки.
При Покупке Дополнительных Кирпичей Это Обходится Дешевле Оптовые пороги могут сделать покупку в большем количестве, чем необходимо, оптимальной, например, выбрать 100 дешевых кирпичей оптом вместо одного очень дорогого кирпича в розницу и выбросить излишки. Таким образом, правильный ответ может находиться в последней строке или под ней, но в столбце, который находится за пределами точного спроса. Только один магазин может рационально превысить спрос; превышение в нескольких магазинах приводит к расточительству. Расширьте таблицу до максимального оптового порога и найдите минимальный в этом расширенном ассортименте.
Сложность и расположение петель для кирпича DP Таблица охватывает магазины по спросу, а также оптовые продажи, и каждая ячейка сканирует все возможные x для текущего магазина, что дает примерно кубическое время. Изменение порядка циклов для итерации по строкам значительно повышает производительность. Размещайте магазины по строкам, а количество блоков - по столбцам для более быстрого доступа. Эта организация устраняет постоянные факторы без изменения алгоритмической идеи.
Подстрока DP для минимального удаления скобок Подстрока - это s[L..R], непрерывный блок. Пусть DP[L][R] - минимальное количество удалений, чтобы сделать s[L..R] правильной последовательностью скобок. Длина - для одной подстроки всегда требуется одно удаление, образующее диагональную основу. Вычисляйте ответы, увеличивая длину подстроки, чтобы убедиться в готовности зависимостей.
Концы в тон в виде свободной обертки Если s[L] − это открывающая скобка, а s[R] - соответствующий закрывающий тип, преобразуйте внутреннюю часть s[L+1..R-1] и оберните ее без дополнительных удалений. Длина - две совпадающие пары уменьшаются до пустого сегмента, который обрабатывается как ноль. Этот специальный перенос применяется всякий раз, когда концы совпадают. Он дополняет, а не заменяет общую стратегию разделения.
Всегда учитывайте все разбиения на две части Любая правильная последовательность скобок может быть сформирована путем объединения двух правильных последовательностей. Попробуйте разделить каждую точку i и возьмите минимальное значение DP[L][i] + DP[i+1][R]. Разбиение на три или более частей не требуется, поскольку рекурсивное двустороннее разбиение уже охватывает эти случаи. Заполнение по длине гарантирует, что подзадачи будут решены заранее.
Как избежать завышения значений в скобке DP Использование только случая совпадающих концов может привести к перерасчету удалений, например, к 2, когда при разбиении получается 0. Всегда оценивайте как специальный перенос, так и все разбиения на две части и выбирайте минимальное значение. Пустые внутренние сегменты рассматриваются как нулевые, когда возникает L+1 > R. Запоминаемая рекурсия может лениво вычислять одни и те же соотношения, но на практике выполняется медленнее.
Шаблон кубической сложности в подстроке DP Существует O (n ^ 2) соответствующих ячеек (верхний треугольник), и в каждой из них учитывается O (n) точек разделения, что дает O (n ^ 3) времени. Окончательный ответ − DP[0][n-1] после установки оснований диагоналей. Многие задачи с подстроками выполняются по этому шаблону: специальная структура плюс исчерпывающие разбиения на две части. Этот шаблон является надежным руководством для таких задач.
Сжатие строк с вложенным повторением Кодируйте, записывая количество повторов и заключая подстроку в круглые скобки, что позволяет выполнять вложенное сжатие. Сжатие только фрагментов одинаковых символов часто неоптимально, поскольку сжатые блоки могут быть сжаты повторно. Примеры с повторяющимися подстроками показывают существенную экономию за счет вложенности. Целью является минимальная длина кодируемого файла, а не просто любое допустимое сжатие.
Переходы DP для оптимального сжатия Пусть DP[L][R] - минимальная кодируемая длина s[L..R]. Всегда старайтесь разделить ее на две части и суммировать их оптимальные кодировки. Также проверьте, состоит ли s[L..R] из k одинаковых блоков, подсчитав делители его длины и проверив равенство блоков. Тогда стоимость равна цифрам(k) + 2 в круглых скобках + DP блока.
Частичное повторение возникает из-за расщепления Если повторяются только некоторые блоки, переходы с разделением на две части уже обеспечивают наилучшее сочетание сжатых и несжатых областей. Перечисление всех позиций вырезания позволяет DP сжимать повторяющийся фрагмент и оставлять остальные как есть или сжимать по-другому. Вложенное повторение естественным образом возникает в результате рекурсивного применения. Никакого дополнительного специального обращения не требуется.
Как на самом деле изучается динамическое программирование Не существует определенной книги, которая помогала бы овладеть навыками чтения DP; прогресс достигается в результате решения множества задач. Решайте более простые задачи, используйте подсказки или редакторские статьи, когда застреваете, и повторяйте их до тех пор, пока шаблоны не станут интуитивно понятными. Код обычно пишется быстро, как только идеи о состоянии и переходе понятны, хотя реконструкция ответов может быть сложной. Нескольких упражнений недостаточно; сотни формируют надежный инстинкт.
Где появляется DP и что считается DP Двухпараметрические задачи часто концептуально отражают одномерные, просто они распространяются на большее количество осей, таких как ячейки сетки или парные префиксы. Классические решения, выходящие за рамки современных задач, включают в себя ранец и DP на деревьях. Даже суммы префиксов или текущие минимумы могут рассматриваться как DP в широком смысле; граница с естественными накоплениями нечеткая. Многие решения могут быть найдены без явного указания их как DP.
Стратегия практической работы, ожидания и сообщество Постепенно повышайте сложность: решайте тренировочные задания, олимпиадные задачи и задачи на разделение, чтобы развить навыки без перегорания. Задачи на собеседовании обычно проще, чем на соревнованиях, а самые спортивные задания редко используются в повседневной разработке. Сложные конкурсные задания - это ценная практика, но они далеки от большинства производственных задач. Задавайте вопросы в Telegram-чате, получайте рекомендации по ресурсам и продолжайте прогрессировать, постоянно практикуясь.