Где применяется
1. Задача
Жадный подход ошибается, когда лучший выбор прямо сейчас мешает лучшему итогу. Тогда помогает динамическое программирование. Задачу делят на маленькие подзадачи, у которых общая работа. Каждую решают один раз, а её ответ потом берут готовым.
У тебя ряд чисел по дням: выручка за каждый день. В некоторые дни были возвраты, и число уходит в минус. Финансовый отдел спрашивает: какие несколько дней подряд вместе дали больше всего денег? Ответом может оказаться и один день, и весь месяц, но обычно это отрезок где-то посередине.
Медленный способ: перебрать каждое начало и каждый конец и сложить каждый отрезок. На месяце это нормально. На данных за несколько лет это ловушка O(n2), которую ты учился замечать ещё на уроке 09.
На этот вопрос можно ответить за один проход. Приём, который это даёт, упрощает много задач, которые выглядят страшно. Этот приём и есть тема урока.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmaxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5])Ищем наибольшую сумму сплошного отрезка. Состояние на i: лучшая сумма отрезка, который кончается ровно на i.
Столбики: сколько раз посчитан ответ для каждой ступеньки i, от 0 до 18.
Одна операция: один вызов или одна клетка таблицы. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(2ⁿ)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- лучшее/максимум/минимум, заканчивающееся в позиции i
- число способов дойти, подняться или замостить
- нельзя брать два соседних элемента
- минимальная стоимость пути по сетке
- повторяющиеся подзадачи, одно и то же состояние считается заново
Похоже, но не то
- Рекурсия с мемоизацией (Recursion with memoization)
Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
- Рекурсия (Recursion)
Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.
n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.
На LeetCode
Задачи, где лучший ответ на позиции i зависит только от ответов на одну или две позиции назад, например ограбление домов, подъём по лестнице или лучший отрезок, который кончается здесь. Два бегущих числа заменяют всю таблицу.
Каждая ступенька стоит меньшего из двух вариантов, прийти с одной или с двух ступенек ниже, плюс её собственная цена.
Это maxSubArray из урока. На каждом числе продолжай отрезок или начинай заново.
Это rob из урока, где взять и пропустить хранятся в двух числах.
Дома стоят по кругу, так что запусти rob дважды, без первого дома и без последнего, и возьми большее.
Сложи очки для каждого значения и запусти rob по значениям, ведь взяв v, ты теряешь v минус 1 и v плюс 1.