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

Привет!

Недавно решал задачи с архива 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}$:
_hcyl9c5amyllphpuilsqzy0pxc.jpeg
Поскольку нам известны все лестницы, которые состоят из меньшего количества кубиков, то «отщепим» от лестницы $(i,j)$ правый столбик. В результате получится лестница c $i-j$ кубиками. Пример для $i = 9, \ j = 4$:
alwkq9vsxwenchkmlyyixnp_7qe.jpeg
Но для таких лестниц результат уже известен, поэтому переберем все такие лестницы циклом по $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 


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

Итак, что мы имеем. Первый энт знает 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. Свойства сравнения по модулю.

© Habrahabr.ru