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

Привет!

Недавно решал задачи с архива 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$ и проанализируем, какие могут быть ситуации:

является полным квадратом. В этом случае $d_{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$ кубиков по правилам:

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

На этот раз будем строить двумерную динамику. Создадим табицу $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

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



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

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

Все энты, которые знают нечетное количество слов, являются старыми и могли научиться только от предыдущих. Поэтому для нечетных 
Что касается энтов, которые знают четное количество слов — так это все те, кто получил столько же слов от эльфов (молодые)  те, кто научился от предыдущих (старые); то есть для четного  имеем .



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

Пример кода на 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;






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

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

    
            © Habrahabr.ru