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

    Привет!

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

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 3

      +3

      По 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.

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

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


          int arr[N][K];
          /* ... */
          arr[i][j] = arr[i + 1][j] * 3 + arr[i + 2][j - 1] * 5 + arr[i][j + 1];
          /* ... */
          cout << arr[i][j] << endl;

          То есть в этом примере не имеет смысла хранить массив именно [N][K] — подойдет [3][K] и считать надо "с конца", без рекурсии. Тогда вместо arr[x][y] надо писать arr[x % 3][y], и так далее.

        Only users with full accounts can post comments. Log in, please.