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

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

P.S.: Ах да. функция calc может работать быстрее. она делает много лишней работы. попробуй догадаться как ее ускорить.

Добавлено через 5 минут

Сообщение от s3lf

Источник

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

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

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

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

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

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

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

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; >

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

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

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

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

Нужно изменить только «начало» нашей динамики. Если первая лестница не приносит нам монет, то желательно перепрыгнуть через нее, однако, если , то лучше наступить и собрать свои монетки. Итак, .

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

Пример 2. В лабиринте имеется комнат, в каждой из которых находится золото (в клетке лежит золота). Задача — определить, какое максимальное количество золота можно собрать при оптимальном маршруте из точки в точку , если идти можно либо вниз, либо направо.

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

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

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

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

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

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

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

1. является полным квадратом. В этом случае .
2. Возможно, предыдущее число было полным квадратом. Тогда .

Поступим следующим образом: будем искать разложение такое, что

Так как — полный квадрат, то , и

то есть мы нашли разбиение, которое просто-напросто лучше, чем , и ответ в этом случае будет

for(int k = 1; k = 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; > 

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

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

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

Поскольку нам известны все лестницы, которые состоят из меньшего количества кубиков, то «отщепим» от лестницы правый столбик. В результате получится лестница c кубиками. Пример для :

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

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

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

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

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 d[i][j] = cnt; > d[i][i] = 1; // добавляем фиктивную лестницу > long answer = 0L; for(int i = 0; i answer--; // вспоминаем про фиктивную лестницу 

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

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

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

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

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

Источник