Динамическое программирование: запоминаем уже решенные подзадачи

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

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

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

Пример с лестницей

Школьник может подниматься на 1 или 2 ступеньки. Сколько способов подняться на n ступенек?

Для первой ступеньки есть 1 способ. Для второй — 2 способа. Для каждой следующей ступеньки ответ равен сумме двух предыдущих: попасть на нее можно с предыдущей ступеньки или через одну.

n = int(input())
dp = [0] * (n + 1)
dp[0] = 1

for step in range(1, n + 1):
    dp[step] += dp[step - 1]

    if step >= 2:
        dp[step] += dp[step - 2]

print(dp[n])

Как узнать динамику

В задаче есть признаки динамического программирования:

• ответ для большого случая зависит от меньших случаев;
• одни и те же подзадачи повторяются;
• можно двигаться слева направо, снизу вверх или от простого состояния к сложному.

Что хранить в массиве dp

Самый важный вопрос: что означает dp[i]? Например, “количество способов добраться до i-й ступеньки” или “лучший результат на первых i элементах”. Если смысл ячейки понятен, формула обычно находится легче.

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

Практикум: максимальный балл на ступенях

На каждой ступени записан балл, двигаться можно на одну или две позиции. Для набора 2, -5, 4, 3, -1 найдите максимальную сумму при достижении последней ступени. Определите состояние best[i], базы и переход до кода. Заполните таблицу вручную и сохраните выбор предка, чтобы восстановить путь. Проверьте одну ступень, две ступени и отрицательные значения: инициализация нулём может создать несуществующий маршрут. Сравните с полным перебором на маленьком наборе как с эталоном.

Контрольная точка

Какая информация о прошлом достаточна для вычисления очередного состояния? Если переход разрешён только с двух предыдущих ступеней, объясните, почему хранение всех маршрутов избыточно, но база для первых позиций обязательна.

Частые вопросы

Как понять, что задача подходит для динамического программирования?

Ищите повторяющиеся подзадачи и возможность выразить лучший или числовой ответ через уже вычисленные состояния. Нужно явно определить смысл состояния, допустимые переходы, базы и порядок вычисления; одного слова «оптимум» недостаточно.