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

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

Краткий ответ

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

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

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

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

Школьник может подниматься на 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 элементах”. Если смысл ячейки понятен, формула обычно находится легче.

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

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

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

https://yadro-code.ru/lessons/without-university/school-programming-basics/school-programming-22