Задание 20: динамическое программирование

Что такое динамическое программирование

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

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

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

Алгоритм решения по шагам

Сначала выбери, что именно будет храниться в таблице. Обозначь это как f(n) или f(i, j). В одномерной задаче индексом может быть номер ступеньки, сумма или позиция. В задаче на поле понадобятся две координаты: строка и столбец.

Затем найди базовые значения. Это самые маленькие случаи, которые можно определить сразу: f(0) = 1, если есть один способ ничего не сделать, или f(1) = 1, если на первую ступеньку ведёт один путь. Ошибка в начальном значении испортит всю таблицу.

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

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

Разобранный пример: маршруты робота

Робот находится в левом нижнем углу таблицы 3 × 4 и может двигаться только вправо или вверх. Сколько существует маршрутов в правый верхний угол? Удобно считать количество путей для каждой клетки, начиная со стартовой.

Стартовая клетка: f(1, 1) = 1
В первой строке: 1, 1, 1, 1
В первом столбце: 1, 1, 1
Внутренние клетки: f(i, j) = f(i − 1, j) + f(i, j − 1)
Вторая строка: 1, 2, 3, 4
Третья строка: 1, 3, 6, 10
Ответ: f(3, 4) = 10

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

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

Другие виды переходов и таблица решений

В заданиях встречаются не только маршруты. Например, на лестницу разрешено наступать на одну или две ступеньки за ход. Тогда количество способов попасть на n-ю ступеньку складывается из способов попасть на две предыдущие:

\( f(n) = f(n - 1) + f(n - 2) \)
\( f(1) = 1, f(2) = 2 \)
\( f(3) = 3, f(4) = 5, f(5) = 8 \)

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

Что ищем	Операция	Типичная формула
Количество способов	Сложение	f = f₁ + f₂
Минимум	Выбор меньшего	f = min(f₁, f₂)
Максимум	Выбор большего	f = max(f₁, f₂)

В записи могут пригодиться обозначения ¾, 2⅓, √, ², × и ·, если задача связана с весами, расстояниями или стоимостью. Но сначала составь смысловую модель, а уже потом выполняй арифметику.

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

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

Третья ошибка — неправильный порядок заполнения. Нельзя использовать значение, которое ещё не найдено. Четвёртая — сложение вариантов, которые пересекаются и могут считать один путь несколько раз. Разделяй варианты по последнему действию или по последнему шагу.

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

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

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

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

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