SavePearlHarbor

Динамическое программирование в олимпиадных задачах

—

от автора

admin
Привет!

Недавно решал задачи с архива Timus Online Judge и наткнулся на раздел под названием задачи динамического программирования. Задачи такого типа вызывают у меня особый интерес, потому что зачастую такой подход обеспечивает быстроту и элегантность решения. Что же такое — динамическое программирование?

Динамическое программирование — это подход к решению задач, при котором происходит разбиение на подзадачи, которые «проще» в сравнении с исходной. Слово «динамический» близко по значению к «индуктивный»: предполагается, что известен ответ для какого-то значения $k$, и хочется найти ответ для $k+1$. В математике это называется индуктивным переходом, и составляет основную идею динамического программирования.

Простые примеры

Наиболее яркой и показательной задачей является задача вычисления $n$-ого числа последовательности Фибоначчи. Известно, что последовательность обладает такими свойствами:

$ F_0 = F_1 = 1,\ F_n = F_{n-1} + F_{n-2}.$

Отсюда сразу вытекает рекуррентная формула:

int Fibonacci(int n) { 	if(n == 1 || n == 2) return 1; 	return Fibonacci(n-1) + Fibonacci(n-2); }

Если рекурсия ищет число «с конца», то следущий метод последовательно вычисляет все числа, расположенные между $0$ и $n$:

int dpFibonacci(int n) { 	int prev1 = 1; 	int prev2 = 1; 	int curr = 0; 	for(int j = 2; j < n; j++) { 		curr = prev1 + prev2; 		prev1 = prev2; 		prev2 = curr; 	} 		return curr; }

Понятно, что при достаточно больших $n$ этот алгоритм работает намного быстрее: он не вычисляет промежуточные значения по нескольку раз. Рассмотрим чуть более сложный пример.

Пример 1. Вы шагаете по платной лестнице. Чтобы наступить на $i$-ую ступеньку, необходимо заплатить $a_i$ монет. Вы можете перешагивать на следующую ступень или перепрыгивать через одну. Задача: пройти $n$ ступенек и потратить как можно меньше монет.

Понятно, что перешагивая через каждую ступень, мы минимизурем количество «платежей», но можем нарваться на очень дорогую ступень, которую хотелось бы избежать. Создадим массив значений $d$, в котором на $j$-ом месте будет (минимальное) число монет, которые необходимо потратить, чтобы добраться до $j$-ой ступеньки. Сразу ясно, что $d_1 = a_1, \ d_2 = a_2$. А дальше будем брать минимум из двух предыдущих ступенек и добавлять стоимость самой ступеньки:

$d_i = \min \left(d_{i-1}, d_{i-2}\right) + a_{i}.$

Немного изменим условия задачи: предположим, что на каких-то ступеньках вы можете получать монеты (это будет означать, что $a_k < 0$). Что необходимо изменить в алгоритме, чтобы он давал правильный результат?

Решение

Нужно изменить только «начало» нашей динамики. Если первая лестница не приносит нам монет, то желательно перепрыгнуть через нее, однако, если $a_1 < 0$, то лучше наступить и собрать свои монетки. Итак, $d_2 = \min\left(0, d_1\right) + a_2$.

Рассмотрим другой пример, в котором используется «двумерная» динамика.

Пример 2. В лабиринте имеется $n\times m$ комнат, в каждой из которых находится золото (в клетке $(i,j)$ лежит $a_{ij}$ золота). Задача — определить, какое максимальное количество золота можно собрать при оптимальном маршруте из точки $(0,0)$ в точку $(n,m)$, если идти можно либо вниз, либо направо.

Итак, мы хотим узнать оптимальный маршрут в клетку $(i,j)$. Сюда мы можем попасть из двух клеток — $(i-1, j)$ и $(i, j-1)$. С учетом того, что оптимальные маршруты для этих двух клеток известны (они хранятся в какой-то таблице $d$), то ответ для клетки $(i,j)$ получается следующим образом:

$ d_{ij} = \max \left(d_{i-1j}, d_{ij-1}\right) + a_{ij}.$

Эта еще одна классическая задача динамического программирования, модификации которой довольно часто встречаются в задачах спортивного программирования. Более подробно аналогичная задача объясняется здесь.

Более сложные задачи

При желании динамический подход можно прикрутить куда вздумается. Рассмотрим задачу с архива Timus Online Judge.

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

Как и раньше, предположим, что нам известны ответы для всех чисел $k-1$, которые хранятся в каком-нибудь массиве $d$, и нам бы хотелось найти $d_{k}$.

Возьмем это число $k$ и проанализируем, какие могут быть ситуации:

  1. $k$ является полным квадратом. В этом случае $d_{k} = 1$.
  2. Возможно, предыдущее число $k-1$ было полным квадратом. Тогда $d_{k} = d_{k-1} + 1$.

Вообще, вариант прибавления единицы к предыдущему кажется не таким уж плохим.

Поступим следующим образом: будем искать разложение $k = q^2 + s$ такое, что

$d_{q^2} + d_s < d_{k-1} + 1.$

Так как $q^2$ — полный квадрат, то $d_{q^2} = 1$, и

$d_s < d_{k-1},$

то есть мы нашли разбиение, которое просто-напросто лучше, чем $d_{k-1} + 1$, и ответ в этом случае будет

$d_k = d_{s} + d_{q^2} = d_s + 1.$

Пример кода на Java, реализующий данный алгоритм:

for(int k = 1; k <= n; k++) { 	int best = d[k - 1] + 1; // принимаем этот вариант за наилучший 	int q = 1; 	while(k - q*q >= 0) {  // k = q*q + s 		if(k - q*q == 0) { // k - полный квадрат 			best = 1; 			break; 		} else if(d[k - q*q] < best) best = d[k - q*q] + 1;  		 		q++; 	} 	d[k] = best; }

Рассмотрим следующую задачу. Цель — построить лестницу из $N$ кубиков по правилам:

  1. лестница имеет минимум две ступени;
  2. лестница не может иметь две одинаковые ступени;
  3. ступени лестницы идут в порядке возрастания (то есть следующая больше, чем предыдущая).

На этот раз будем строить двумерную динамику. Создадим табицу $d$, в которой на позиции $(i,j)$ будет лежать количество лестниц, состоящих из $i$ кубиков, высота которых не превосходит $j$. Если получится, то ответом к нашей задаче будет сумма

$\sum\limits_{j=1}^n d_{nj}.$

Итак, будем решать задачу по нахождению количества лестниц, составленных из $i$ кубиков, которые имеют высоту $j$. На картинке показаны лестницы, которые попадут в $d_{74}$:

Поскольку нам известны все лестницы, которые состоят из меньшего количества кубиков, то «отщепим» от лестницы $(i,j)$ правый столбик. В результате получится лестница c $i-j$ кубиками. Пример для $i = 9, \ j = 4$:

Но для таких лестниц результат уже известен, поэтому переберем все такие лестницы циклом по $k$ и сложим все результаты. Таким образом,

$d_{ij} = \sum\limits_{k=1}^{j-1} d_{i-jk}.$

Теперь будем перебирать высоты лестниц:

$d_{ij} = \sum\limits_{k=1}^{j-1} d_{i-jk}, \ j = \overline{1,i}.$

Окончательно, изменяя $i$ от $1$ до $n$, получим ответ.

Важно: в процессе построения нашей матрицы необходимо учитывать $d_{ii} = 1$, так как в противном случае будут «теряться» некоторые виды лестниц (при «отщеплении»), но разумеется, что такая лестница не удовлетворяет условиям задачи, поэтому в ответе будет число $d_{nn} - 1$.

Пример кода на Java, реализующий данный алгоритм:

dp = new long[n + 1][n+1]; d[1][1] = 1; d[2][1] = 0; d[2][2] = 1; for(int i = 3; i < n + 1; i++) { 	for(int j = 2; j <i; j++) { 		long cnt = 0; 		for(int k = 1; k < j; k++) { 			cnt += d[i - j][k]; 		} 		d[i][j] = cnt; 	} 	d[i][i] = 1; // добавляем фиктивную лестницу 			 }  long answer = 0L; for(int i = 0; i <= n; i++) { 	answer += d[n][i]; } answer--; // вспоминаем про фиктивную лестницу

Следующая задача решается с использованием одномерного массива.

Итак, что мы имеем. Первый энт знает 2 слова. Каждый энт обучает всем словам, которые знает сам, двух энтов: молодого и старого. В свою очередь, молодого обучили еще стольким же словам, сколько он уже знает, а старого обучили только одному слову. Необходимо узнать, сколько энтов знает в точности $K$ слов (необходимо вывести число этих энтов по модулю $P$).

Решение довольно простое. Создадим массив $d$, в котором на $i$-ом месте будем хранить количество энтов (по модулю $P$), которые знают $i$ слов. Все начинается с первого энта, который знает два слова, поэтому $d_2 = 1$. А дальше все просто:

  • Все энты, которые знают нечетное количество слов, являются старыми и могли научиться только от предыдущих. Поэтому для нечетных $i: \ d_i = d_{i-1};$
  • Что касается энтов, которые знают четное количество слов — так это все те, кто получил столько же слов от эльфов (молодые) $+$ те, кто научился от предыдущих (старые); то есть для четного $i$ имеем $d_i = d_{{i\backslash 2}} + d_{i-1}$.

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

Пример кода на Java, реализующий данный алгоритм:

int[] d = new int[K + 1]; if(K >= 2) d[2] = 1; if(P != 1) { 	for(int i = 3; i <= K; i++) { 		if(i % 2 != 0) { 			d[i] = d[i - 1]; 		} 		else { 			d[i] = ((d[i/2] % P) + d[i - 1] % P) % P; 		} 	} } else d[K] = 0;

Используемые ресурсы:

  1. Timus Online Judge;
  2. Немного о динамическом программировании;
  3. Свойства сравнения по модулю.


ссылка на оригинал статьи https://habr.com/post/418867/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *