Не понимаю динамическое программирование

Почему динамическое программирование кажется непонятным

Ты видишь задачу про лестницу, рюкзак или последовательность, читаешь решение и думаешь: «Откуда взялась эта таблица и почему ответ складывают именно так?» Это нормальная реакция: динамическое программирование не является одной формулой, а представляет собой способ разбить большую задачу на маленькие. В этом разборе ты научишься находить состояние, переход и порядок вычислений, а затем проверишь идею на полном примере.

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

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

Шаг 1. Состояние и базовые случаи

Состояние — это короткое описание подзадачи, ответ на которую мы хотим сохранить. Например, пусть dp[i] означает количество способов добраться до ступеньки i, если можно подниматься на одну или две ступеньки. Важно не просто назвать массив dp, а словами объяснить смысл каждого элемента. Если смысл не сформулирован, переход почти наверняка получится случайным.

Затем ищем базовые случаи — самые маленькие значения, которые можно определить без общей формулы. На нулевую ступеньку можно считать, что есть один способ: ничего не делать. До первой ступеньки можно добраться одним способом. После этого на ступеньку i приходят либо с i − 1, либо с i − 2.

\( dp[0] = 1 \)
\( dp[1] = 1 \)
\( dp[i] = dp[i - 1] + dp[i - 2], i \ge 2 \)

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

Шаг 2. Как строится переход

Переход отвечает на вопрос: из каких предыдущих состояний получается текущее? Рассмотрим более содержательную задачу. Есть числа 2, 3, 7 и сумма S. Нужно посчитать минимальное количество чисел, из которых можно составить S. Один и тот же элемент разрешается использовать несколько раз.

Определим dp[s] как минимальное количество чисел, дающее сумму s. Последнее выбранное число может быть 2, 3 или 7. Значит, перед ним уже была сумма s − 2, s − 3 или s − 7. К каждому предыдущему ответу добавляется единица за последнее число.

\( dp[0] = 0 \)
\( dp[s] = min(dp[s - 2], dp[s - 3], dp[s - 7]) + 1 \)
учитываем только переходы, где s − число ≥ 0

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

После определения перехода проверь его на одной сумме вручную. Для s = 7 можно выбрать одно число 7, поэтому dp[7] = 1. Такая проверка быстро обнаруживает пропущенный переход или неверный базовый случай.

Полный пример: максимум в рюкзаке

Есть рюкзак вместимостью 7 кг и три предмета: первый весит 3 кг и стоит 4 условные единицы, второй весит 4 кг и стоит 5, третий весит 5 кг и стоит 7. Каждый предмет можно взять не больше одного раза. Обозначим dp[i][w] — максимальную стоимость среди первых i предметов при вместимости w.

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

dp[i][w] = dp[i − 1][w], если предмет не берём
dp[i][w] = max(dp[i − 1][w], dp[i − 1][w − weight] + value), если берём
для первого предмета: dp[1][3] = max(0, 0 + 4) = 4
для второго при w = 7: dp[2][7] = max(4, dp[1][3] + 5) = 9
для третьего при w = 7: dp[3][7] = max(9, dp[2][2] + 7) = 9

Ответ 9: выгоднее взять первый и второй предметы, их общий вес равен 7. Последний переход показывает важный принцип: решение сравнивает варианты, а не пытается угадать единственную комбинацию заранее.

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

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

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

Что проверить	Вопрос к себе
Состояние	Что именно означает dp?
База	Как решаются самые маленькие случаи?
Переход	Из каких вариантов выбирается ответ?
Порядок	Все нужные значения уже посчитаны?

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

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

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

Закрепить тему можно в личном кабинете: зарегистрируйся и реши 5 заданий бесплатно. Начни с задач на лестницу и рюкзак, а затем сравни свои состояния и переходы с разбором. Дополнительные варианты для экзамена можно найти в разделах ОГЭ и ЕГЭ.