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

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

Задачи на последовательности, маршруты и выбор предметов часто выглядят как длинный перебор: кажется, что нужно проверить все варианты и легко потеряться в вычислениях. Динамическое программирование помогает увидеть повторяющуюся закономерность, сохранить уже найденные ответы и превратить сложную задачу в цепочку понятных шагов. Разберём, как распознавать такие задачи, строить таблицу и проверять результат.

Название метода не связано с движением или физикой. «Динамическое» означает постепенное развитие решения, а «программирование» — планирование вычислений. В школьной математике этот подход полезен не только в алгоритмах: он тренирует внимательность к условиям, умение находить связь между соседними случаями и объяснять ход рассуждений.

Главная идея проста: ответ для большого случая строится на ответах для меньших случаев. Например, число способов добраться до клетки зависит от способов попасть в клетки перед ней. Если одна и та же маленькая задача встречается много раз, её результат достаточно вычислить один раз.

Как распознать закономерность

Сначала определи, что именно меняется от шага к шагу. Это может быть номер клетки, длина последовательности, сумма набранных очков или количество выбранных предметов. Такой параметр называют состоянием. Обозначим ответ для состояния n как f(n).

Затем выясни, из каких предыдущих состояний получается новое. Если разрешены шаги на 1 или 2 клетки, то попасть в клетку n можно из n − 1 или n − 2. Значит, значение f(n) связано с двумя предыдущими значениями. Это и есть переход.

Не менее важны начальные значения. Они описывают самые маленькие случаи: стартовую клетку, пустую последовательность или нулевую сумму. Ошибка в начале обычно портит всю таблицу, поэтому основания нужно проверять отдельно.

\( f(n) = f(n - 1) + f(n - 2) \)
\( f(0) = 1, f(1) = 1 \)
\( f(2) = 1 + 1 = 2 \)

Разобранный пример: лестница

Пусть ученик поднимается по лестнице из 5 ступеней. За один ход можно подняться на одну или две ступени. Сколькими способами можно оказаться на верхней ступени? Порядок шагов важен: 1 + 2 и 2 + 1 — разные способы.

Введём f(n) — число способов попасть на ступень n. На последнем ходу ученик либо приходит с соседней ступени, либо перепрыгивает через одну. Поэтому f(n) = f(n − 1) + f(n − 2). На нулевую ступень условно существует один способ: не сделать ни одного шага.

\( f(0) = 1 \)
\( f(1) = 1 \)
\( f(2) = f(1) + f(0) = 1 + 1 = 2 \)
\( f(3) = f(2) + f(1) = 2 + 1 = 3 \)
\( f(4) = f(3) + f(2) = 3 + 2 = 5 \)
\( f(5) = f(4) + f(3) = 5 + 3 = 8 \)
Ответ: 8 способов

Проверка перечислением подтверждает результат: 1 + 1 + 1 + 1 + 1; 1 + 1 + 1 + 2 и перестановки; 1 + 2 + 2 и перестановки; 2 + 2 + 1. Всего получается 8 последовательностей.

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

Таблица и другие переходы

В задачах на максимальную сумму или минимальную стоимость значение состояния не складывают автоматически. Сначала перечисляют допустимые варианты последнего действия, а затем выбирают лучший: максимум — если требуется наибольший результат, минимум — если требуется наименьший.

Тип задачи	Смысл состояния	Операция перехода
Лестница	Число способов попасть на n	Сумма предыдущих значений
Маршрут	Минимальная стоимость клетки	Минимум из соседей + стоимость
Выбор предметов	Лучший результат при ограничении	Максимум: взять или пропустить

Например, если в клетку можно прийти сверху или слева, то минимальная стоимость описывается так: g(i, j) = цена клетки + min(g(i − 1, j), g(i, j − 1)). В первой строке и первом столбце переходы особые: туда часто ведёт только один путь.

Для задач выбора полезно составлять таблицу по двум параметрам: сколько предметов рассмотрено и какой вес или бюджет доступен. Так закономерность становится видимой, а случайный перебор заменяется аккуратным заполнением.

Если хочется потренироваться на похожих переходах, в личном кабинете доступна бесплатная практика с постепенным усложнением задач.

Типичные ошибки и проверка

Первая ошибка — неверно выбрать состояние. Если в нём не хватает информации для продолжения, переход окажется неправильным. В задаче о рюкзаке недостаточно хранить только номер предмета: нужно учитывать оставшийся вес.

Вторая ошибка — перепутать количество способов и лучший результат. Для количества вариантов используется сложение, а для максимальной суммы — сравнение вариантов. Нельзя применять одну и ту же формулу к разным требованиям задачи.

Третья ошибка — забыть про границы. При n = 0 обращение к f(n − 2) невозможно, поэтому начальные значения задают отдельно. Также проверь, разрешены ли пустой путь, повторное использование предмета и движение назад.

Для самопроверки посчитай первые три-четыре значения вручную, проверь крайние случаи и сравни результат с небольшим перебором. Если таблица даёт отрицательное число способов или результат хуже очевидного допустимого варианта, переход нужно пересмотреть.

Разобрать ещё несколько форматов задач можно через бесплатные задания в профиле, а подбор экзаменационных тем есть на страницах ОГЭ и ЕГЭ.

Что запомнить

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

Полезный алгоритм решения: прочитать условие; понять, что означает f; разобрать последний шаг; записать основания; вычислить несколько строк; проверить границы и смысл ответа. Не стремись сразу запомнить готовую формулу: одна и та же закономерность может выглядеть по-разному в задачах о маршрутах, последовательностях и выборе.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно. После каждого решения объясни переход обычными словами: это закрепит не только вычисления, но и сам способ мышления.