01.08.2018 05:07
supreme13 1 3600 Источник
Привет!

Недавно решал задачи с архива 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. Свойства сравнения по модулю.

Комментарии (1)


  1. Izaron
    01.08.2018 23:01
    #18948463

    По 1-й задаче — N-ое число Фибоначчи (с условиями — например не само число, которое ни в какие ворота не влезет, а его остаток от деления на MOD=10^9+7) можно еще нескучно находить за O(log(N)) времени, то есть почти бесплатно, даже если N = 10^9 или 10^18 =)


    Магия

    Матрица преобразования размером 2x2 с одним нулем и тремя единицами меняет (a, b) на (b, a + b), то есть на следующую пару Фибоначчи.
    Чтобы X раз применить эту матрицу к (a, b) = (0, 1), можно не перемножать по очереди, а сразу найти X^(N-2) бинарным возведением в степень, и применить! После каждого умножения надо только ко всем элементам применить %= MOD.