Динамическое программирование
автор: Лосева Ирина Алексеевна

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

1. В задаче можно разумно выделить подзадачи аналогичной структуры меньшего размера. Иногда бывает, что исходящая задача не является одной из задач серии, но ее можно легко решить, опираясь на решения одной или нескольких задач серии.
2. Среди выделенных подзадач есть тривиальные, т.е. имеющие «малый размер» и очевидное решение.
3. Оптимальное решение подзадачи большего размера можно построить из оптимальных решений подзадач (классическая формулировка: у оптимально решенной задачи все подзадачи решены оптимально).
4. При решении различных подзадач приходится многократно решать одни и те же (нетривиальные) подзадачи меньшего размера (подзадачи прерываются). Действительно, только при этих условиях есть смысл запоминать какие-либо промежуточные результаты.
5. Таблицы для запоминания ответов подзадач имеют разумные, не слишком большие, размеры.

 Черепашка

Формат входных данных

Формат выходных данных

    Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора «Черепашки». Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен «максимальный» путь для всех клеток, кроме правой нижней (функция F (X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:

 Function F (x, y: integer) : longint;
 Begin
 If B [x, y] = -1 then
 If F(x-1, y) > F(x, y-1)
 Then B [x, y]: = F(x-1, y) + A[x, y]
 Else B [x, y]: = F(x, y-1) + A[x, y];
 F : = B [x, y]
End;

  For i: =1 to N do
 For j: =1 to N do
 If B [i-1, j] >B[i,j-1]
 Then B[i, j] : = B [i-1, j] + A[i, j] 
 Else B[i, j] : = B[i,j-1] + A[i, j];

 Гвоздики

Формат входных данных

Формат выходных данных

Пример

    Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек a_k). 
 

    Можно считать, что любая ниточка связывает два соседних гвоздика (иначе ее можно разрезать на несколько частей, связывающих все гвоздики между теми, которые связывала наша ниточка изначально). 
    Научимся вычислять a_k. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним (k-m) и предпоследним ((k-1)-m)гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-m) и предпредпоследним ((k-2)-m) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков удовлетворяют условию задачи, во втором - первые k-2. Значит a_k=min(a_k-1,a_k-2)+l_k-1,k, где l_k-1,k - расстояние между k-m иk-1-м гвоздиками (в отсортированном массиве). Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно (в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000). Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе a_N.
 

    Число действий, выполненных данным алгоритмом, пропорционально N.
 

Лесенки

Формат входных данных

Формат выходных данных

Пример

    Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.
---
1 | |
---------
4 | | | | |
-----------
5 | | | | | |
-----------------
8 | | | | | | | | |
-----------------
n=1+4+5+8 
    Пусть в качестве первого слагаемого мы взяли L, тогда нам требуется n-L разбить на слагаемые. Но теперь добавляется дополнительное условие - слагаемые должны быть больше либо равны L+1. Значит, нам достаточно научиться считать число разбиений числа n на слагаемые не меньшие k(обозначим an, k). Есть два случая: слагаемое k либо входит в разбиение (таких способов an-k, k+1), либо нет (таких способов an, k+1). Так как никакое разбиение не подходит одновременно под оба эти случая, то an,k=an-k, k+1 + an, k+1. Заметим, что для единицы существует единственное разбиение: 1 = 1. Значит a1, 0 = a1, 1 = 1, a1, f = 0, где f >= 2. an, k удобно вычислять в порядке невозрастания k. При равных k - в произвольном порядке.
    Данный алгоритм выполняет порядка N² действий.

Эксперимент

Входные данные:

Выходные данные:

Пример:

Робот

Формат входных данных

Формат выходных данных

 Type T 1 = array [- 16.. 16, - 16..16] of Longint;
 T2 = array [0.. 16] of ^ T 1;
 Var D: T2;

 Function F (X: integer) : longint;

 Var s : longint;
 Begin
 If D [Z]^[X,Y] = -1 then 
 Begin
 S: = 0;
 If X< > -16 then S:= s+ F (X-1, Y, Z-1); 
 If X< > 16 then S: = s+ F (X+1,Y, Z-1);
 If Y< > -16 then S: = s+ F (X, Y-1, Z-1);
 If Y< > 16 then S: = s+ F (X, Y+1, Z-1);
 D [Z]^[X,Y] = s
 End;
 F: = D [Z]^[X,Y]
End;

For z : =1 to k do
Begin 
 Way2: = Way1 
 For i : =-16 to 16 do
 For J : =-16 to 16 do
 Begin
 S: = 0;
 If I < > -16 then S: = s+ Way2 [i-1, j];
 If I < > 16 then S: = s+ Way2 [i+1, j];
 If J< > -16 then S: = s+ Way2 [i, j-1];
 If J< > 16 then S: = s+ Way2 [i, j+1];
 Way1[i, j] : = s
 End;
End;