Динамическое программирование: основы

Динамическое программирование: состояния, переходы, база — лестница и максимальный подотрезок.

Динамическое программирование (ДП) — метод решения задач, которые разбиваются на перекрывающиеся подзадачи: каждую подзадачу решаем ОДИН раз и запоминаем ответ. Рецепт из трёх вопросов: 1. Состояние: что такое dp[i]? (словами, точно!) 2. Переходы: как dp[i] выражается через меньшие состояния? 3. База: чему равны самые маленькие состояния? Hello-world ДП — лестница: вы стоите внизу лестницы из n ступеней и шагаете на 1 или 2 ступени. Сколько способов подняться? • dp[i] — число способов добраться до ступени i; • на ступень i приходят со ступени i-1 или i-2, значит dp[i] = dp[i-1] + dp[i-2]; • база: dp[0] = 1 (стоим внизу), dp[1] = 1.

Попробуйте сами — код можно менять

Входные данные (пример — можно менять)

Лестница. Введите n до 80, например: 10

Для n = 10 ответ 89 — это числа Фибоначчи, выросшие из задачи сами собой. Два стиля записи ДП: • табличный (как выше): заполняем массив от базы вверх; • мемоизация: пишем рекурсию и кешируем ответы. Что удобнее — дело вкуса, сложность одинакова. Вторая классика — максимальная сумма подотрезка (алгоритм Кадане). Состояние: dp[i] — максимальная сумма подотрезка, ЗАКАНЧИВАЮЩЕГОСЯ в i. Переход: либо продолжаем предыдущий отрезок, либо начинаем новый с a[i].

Попробуйте сами — код можно менять

Входные данные (пример — можно менять)

Максимальный подотрезок. Введите: 8, затем -2 1 -3 4 -1 2 1 -5

Ответ на примере: 6 (подотрезок 4 -1 2 1). Заметьте: dp-массив здесь схлопнулся в одну переменную cur — так часто бывает, когда переход смотрит только на предыдущее состояние. Задание: решите «лестницу», если наступать на некоторые ступени запрещено (dp[i] = 0 для запрещённых). И подумайте, как изменится задача при шагах 1, 2 и 3. Отметьте урок пройденным — Уровень 4 завершён. Впереди продвинутое ДП!