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

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

Задача 02-1. Минимальный путь в таблице

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунд

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

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

Формат входных данных
Во входном файле задано два числа N и M - размеры таблицы (1 <= N <= 20, 1 <= M <= 20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Формат выходных данных
В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол.

Пример

input.txt	output.txt
3 4 1 1 1 1 5 2 2 100 9 4 2 1	8

Разбор

Будем решать более общую задачу (что, как ни странно, зачастую оказывается проще), а именно найдем цену bi,j минимального пути из правой верхней клетки (автор, видимо, ошибся, и имел в виду правую нижнюю клетку) в клетку (i,j). Заметим, что попасть в клетку (i,j) мы могли только из клеток (i-1,j) и (i,j-1). Значит, задачу можно свести к решению подзадач для клеток (i-1,j) и (i,j-1).

Результаты решения подзадач удобно хранить в таблице b размером NxM. Тогда bi,j=min(bi-1,j,bi,j-1)+ai,j ( здесь a - таблица из условия). Применить эту формулу не составляет труда, если bi-1,j и bi,j-1 уже посчитаны. А это легко достигается, если заполнять таблицу b слева направо сверху вниз (т.е. сначала слева направо заполняется первая строка, затем вторая и т.д.). Заметим, что для первой строки и первого столбца формула работает плохо, т.к. там появляются несуществующие элементы таблицы. Их можно заполнить в самом начале, поскольку в каждую из этих клеток можно попасть только одним способом. Ответ на поставленную задачу будет находиться в правом нижнем углу таблицы b.

Количество действий, выполненных этим алгоритмом, пропорционально числу клеток в таблице.

Задача 02-2. "Гвоздики"

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунды

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

Формат входных данных
В первой строке входного файла записано число N - количество гвоздиков (1 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Формат выходных данных
В выходной файл нужно вывести единственное число - минимальную суммарную длину всех ниточек.

Пример

input.txt	output.txt
5 4 10 0 12 2	6

Разбор

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

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

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

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

Задача 02-3. "Подпоследовательности"

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунды

Дана последовательность, требуется найти длину наибольшей возрастающей подпоследовательности.

Формат входных данных
В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

Формат выходных данных
В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.

Пример

input.txt	output.txt
6 3 29 5 5 28 6	3

Разбор

Пусть c1,c2, ... ,cn, - данная последовательность. Покажем, как найти длину максимальной возрастающей подпоследовательности, заканчивающуюся в элементе ck (обозначим ak). Предположим, она уже найдена. Удалим из нее последний элемент. Полученная подпоследовательность является максимальной возрастающей подпоследовательностью, оканчивающейся в некотором элементе cj (j < k). Значит, либо ak = max{j < k, cj < ck}{aj} + 1, либо ak = 1, если таких j не существует. Ответом на поставленную задачу будет максимум из всех ak.

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

Задача 02-4. "Лесенки"

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунды

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

---

| |

---------

| | | | |

-----------

| | | | | |

-----------------

| | | | | | | | |

-----------------

Подсчитать число лесенок, которое можно построить из N кубиков.

Формат входных данных
Во входном файле записано число N (1 <= N <= 100).

Формат выходных данных
В выходной файл вывести искомое число лесенок.

Пример

input.txt	output.txt
3	2

Разбор

Переформулируем нашу задачу на язык математики. В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их 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 - в произвольном порядке.

Данный алгоритм выполняет порядка N2 действий.

Мы рассмотрели несколько задач на метод динамического программирования. Решения, не сложные в написании, порой напоминали какие-то фокусы, которые непонятно как придумать. Умение видеть, какие дополнительные параметры нужно ввести в задачу приходит с опытом. Поэтому давайте рассмотрим еще несколько примеров задач на динамическое программирование.

Задача 03-1. Восстановление скобок

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунды

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

Формат входных данных
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.

Формат выходных данных
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2*10^9.

Пример

input.txt	output.txt
????(?	2

Разбор

Пусть дана скобочная последовательность. Заведем счетчик, равный изначально нулю. Теперь будем двигаться по нашей последовательности и увеличивать счетчик, если встретили открывающуюся скобку и уменьшать в противном случае. Если счетчик всегда был неотрицательный и в конце стал равен 0, то данная скобочная последовательность является правильной. Значение этого счетчика после обработки данного элемента последовательности будем называть "балансом" части последовательности с первого по данный элемент.

Будем решать задачу нахождения количества скобочных последовательностей, удовлетворяющих первым k символам шаблона, у которых баланс всегда неотрицателен и в конце равен m (обозначим количество таких последовательностей ak,m). Есть два варианта: либо на k-м месте стоит открывающаяся скобка, тогда последовательность из k-1 скобки (без последней) должна иметь баланс m-1 - таких последовательностей ak-1,m-1, либо закрывающаяся - тогда, наоборот, баланс последовательности без последней скобки равен m+1 - таких последовательностей ak-1,m+1. В зависимости от шаблона и баланса возможны один, два (если в шаблоне стоит на этом месте ?) или ноль из этих вариантов. ak,m равно их сумме. Ответ на поставленную задачу будет в an,0.

Нужно отметить одну тонкость. В условии сказано, что окончательный ответ входит в стандартный тип longint, но не сказано, что все промежуточные вычисления укладываются в longint. Однако, если в ходе вычислений мы получили какое-то большое число, то оно не может влиять на окончательный ответ (так как при вычислении ответа используется только сумма). Значит, это число можно либо вообще не вычислять, либо вычислить с ошибками. На окончательный результат это не повлияет.

Задача 03-2. Шаблон и слово

Имя входного файла	input.txt
Имя выходного файла	output.txt
Максимальное время работы на одном тесте:	3 секунды

Будем рассматривать слова из больших латинских букв и шаблоны, состоящие из больших латинских букв и символов "?" и "*". Говорят, что слово подходит под шаблон, если в шаблоне можно заменить каждый символ "?" на большую латинскую букву, а каждый символ "*" - на последовательность (возможно, пустую) больших латинских букв, так, чтобы получилось требуемое слово. Напишите программу, которая определит, подходит ли слово под шаблон.

Формат входных данных
В первых двух строках записаны шаблон и слово: в одной строке записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 256 символов).

Формат выходных данных
Вывести YES, если слово подходит или NO, если нет.

Пример

input.txt	output.txt
ABBCDA A*CDA	YES

Разбор

Для начала определим, какая из введенных строк является словом, а какая - шаблоном. Та строка, в которой есть символы '?' или '*' - шаблон. Если ни в одной из строк их нет, то в качестве шаблона возьмем произвольную. Будем определять, может ли часть слова (обозначим s1)с 1-го по k-й символ соответствовать части шаблона (обозначим s2)с 1-го по m-й символ (обозначим ak,m). Теперь есть 3 варианта:

• В шаблоне на m-м месте стоит буква. Тогда она соответствует последней букве слова и ak,m=(s1[k]=s2[m]) and ak-1,m-1
• В шаблоне на последнем месте стоит '?'. Тогда он соответствует последней букве слова и ak,m=ak-1,m-1
• В шаблоне на последнем месте стоит '*'. Тогда возможны два варианта: либо этой звездочке соответсвует пустая последовательность букв слова, либо непустая. Во втором случае в части слова с 1-го по k-1-й символ этой звездочке тоже соответствует некоторая последовательность букв (возможно пустая). Таким образом ak,m=ak-1,m or ak,m-1.

Осталось рассмотреть несколько моментов. Так как '*' может соответствовать пустая последовательность букв, то непустому шаблону вполне может соответствовать пустое слово, значит матрица a должна индексироваться не от 1, а от 0. Если же один из индексов отрицательный - то это всегда FALSE.

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