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

[@Progrik]

>> Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.
Где же вы раньше то были? =( У меня за решение такой задачи оригинальным методом за экзамен по программированию пять автоматом ставили…

[@dezconnect]

Самому то додуматься не судьба конечно. Зато будете потом кичиться высшим образованием.

[@uncleLem]

А Вы во время учебы самостоятельно додумывались до решения абсолютно всех задач? Позволю себе роскошь не поверить.

[@dezconnect]

Да я лучший в группе. Все делал не только себе, но и другим всегда помогал. И ничего сложного в программе ВУЗов нет.

[@cybrid]

К сожалению, я сам не смог решить такую задачу, когда она мне попалась на олимпиаде. Вот сейчас пытаюсь систематизировать материал по ДП.

[@shalex9154]

Такую задачу можно решить быстрее не за N^2 и без дополнительной памяти, а за NlogN, использую бинарный поиск + хеши ;) Если интересно могу написать решение.

[@cybrid]

Интересно, но хочется и самому сначала подумать :)

[@metar]

Если что, хорошая динамика в этой задаче работает за O(N) и с O(N) дополнительной памяти. Проверено на задаче с Тимуса.

[@apangin]

Это как бы другая задача. Разницы не заметили?

[@metar]

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

[@apangin]

И какой у вас алгоритм для задачи с Тимуса?

[@Skiminok]

По-моему, он известен только один классический (если я неправ, metar меня поправит и расскажет свой).
Вкратце: для каждого символа динамикой будем считать две величины — длину длиннейших нечетного и четного палиндрома с центром в данном символе. Тогда при линейном проходе можно смотреть, укладывается ли текущий символ в самый правый найденный доселе палиндром. Если нет — ищем втупую, если да — смотрим на уже вычисленное значение для симметричной буквы в «большом» (самом правом) палиндроме, обрезаем это число до границ большого, если надо, а дальше ищем втупую. Получается именно что O(N) времени (каждый проход втупую один раз затрагивает каждый символ при расширении вправо) и O(N) памяти (два массива).

[@cybrid]

Подумал, никаких идей. Так что буду благодарен, если вы напишете решение.

[@shalex9154]

Могу подтолкнуть, вначале используя позиционный хеш, считаем его для всей строки за О(n). Потом простыми арифметическими манипуляциями можно получить его для любой подстроки за O(1). Делаем обход по строке и фиксируем центр палиндрома(стоит не забывать что длина палиндрома может быть чётной или нечётной), далее используя бинарный поиск ищем длину палиндрома(очевидно что если мы найдем палиндром длины 4, то не исключено что если добавить по 2 символа с обеих сторон, может получиться тоже палиндром).
Если нужен код могу скинуть, но я не фанат такого ;)

[@shalex9154]

Ой, только что почитал выше топик и понял как я лажанул, это работает если палиндром подстрока а не подпоследовательность (

[@apangin]

Равенство хэшей не гарантирует равенства строк. Поэтому либо нужен дополнительный проход для проверки строк (и сложность становится порядка N^2), либо вы утверждаете, что решаете задачу за O(N*logN) с некоторой вероятностью (может, даже большой, но отличной от 1).

[@Skiminok]

Гм. С интересом послушаю.
Решение за O(N log N) с бинпоиском и хэшами для длиннейшего палиндрома-подстроки знаю, для палиндрома-подпоследовательности — никогда не видел… Посидел немного, подумал — не получается же, не хватает информации, как ни крути, хэши работают с неразрываемыми подстроками символов.

[@Skiminok]

А, пока писал коммент, вы уже заметили ошибку :)

[@koka]

Ху*ня

[@mihaild]

[@koka]

Блин всем сорри не сам коментил((( стоит оставить залогиненым акаунт(

[@Brand]

Настолько приелась эта тема, что аж тошно от ДП. Тем более, в период олимпиад)
В любом случае, классика неплохо разобрана.

[@cybrid]

Как мне показалось, сейчас на олимпиадах серьезного уровня есть тенденция ухода от ДП. По крайней мере от динамического программирования в чистом виде. Так что можете радоваться :)

[@agul]

Да? Во всяком случае, в школьных олимпиадах динамику пытаются сунуть туда, где она вообще не нужна.

[@mydoom]

>число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально
а что, простите, имеется в виду (я про «скоростью роста» ЧФ)?

[@cybrid]

Под скоростью роста я подразумевал соотношение F_n и n при увеличении n. Можно рассматривать F_n / n или, например, log F_n / n

[@vanxant]

Хорошо написано. Я давно уже не олимпиадник и нет времени следить за этим спортом, но с удовольствием бы прочел всю теорию из вашей книги. Просто чтобы быть «в тонусе».

[@cybrid]

Спасибо. В планах охватить основные разделы олимпиадного программирования. Первыми на очереди — динамическое программирование по профилю и геометрия.

[@alexeygrigorev]

Здорово, остальные главы из книги тоже будут опубликованы? Буду следить с интересом. Спасибо за хороший материал, вспомнил, как сам на олимпиадах участвовал.

[@cybrid]

Да, планирую продолжить публикацию. Не обещаю, что это будет быстро.

[@Zealint]

На вашем месте я бы не стал рассматривать тривиальные упражнения в учебном пособии. Эти задачи встречаются очень уж часто и слишком простые, чтобы показать реальную силу ДП. Например, возьмите задачу 4 и рассмотрите решение за O(n*log(n)), а не за O(n²), как сейчас. В последней задаче можно дополнительно написать, как вместо матрицы хранить только один массив (или хранить матрицу, но не заводить вторую для получения ответа). Это уже будет куда лучше.

Нас в свое время учили ДП, начиная с задачи про две кучи монет — разбить множество монет на две кучи так, чтобы они были наиболее близкими по стоимости. За линейную память. А тривиальные упражнения можно взять в книге Кормена, например, в гугле запросу «Динамическое программирование» можно подобной ерунды насобирать целый вагон. Без обид.

Какие задачи включить в данный раздел? Ну, те же две кучи монет. Наибольшая возрастающая подпоследовательность за O(n*lon(n)). Динамику по профилю обязательно. Какую-нибудь динамику по подмножествам, например, точное решение задачи Коммивояжера. Вообще, можно брать все, что плохо или мало описано в других источниках. Если вы конечно не претендуете на монографию с полным обзором всех таких задач за последние 70 лет (метод матрицы переноса, он же динамика по профилю был известен ещё в 40-х годах, применялся для точного решения модели Изинга без воздействия внешнего поля).

[@cybrid]

Спасибо за подробный совет. Почему я включаю тривиальные задачи? Чтобы научиться решать сложные задачи, надо с чего-то начинать. На практике я для некоторых задач стараюсь дать несколько уровней сложности — чтобы, например, на первом уровне проходил алгоритм за O(n²), а на втором уже только за O(n * log(n)).
В планах задача о рюкзаке и динамика по профилю. Но в последней после статьи Василевского, мне кажется, сложно сказать что-то новое. Собираюсь включить ДП по профилю только из соображений системности изложения.
Про две кучи монет — спасибо. Как-то эта задача прошла мимо меня.

[@Skiminok]

Что-то новое сказать в динамике по профилю элементарно. Василевский, к примеру, ни звуком не заикается о том, что понятие «профиль» — это произвольное состояние, характеризирующее множество битмаской, а не только всяческие строки и столбцы в двумерном массиве. Видел пару человек, которые начитались Василевского, потом сталкивались с динамикой по состояниям, и у них немного сносило мозг и рвало шаблон: «А где же тут таблица-то?»

На Топкодере в 500 Div 1 очень любят часто динамику по состояниям. К примеру, Gifts.

[@Achilles]

Посоветуйте, где лучше ето все таки разобрать (динамика по [изломаному] профилю). Или кикую-то литературу по етому делу.

[@Zealint]

Чтобы научиться решать сложные задачи, надо с чего-то начинать.

Так вот я вам и говорю, что именно эти задачи, что вы предлагаете, слишком часто обсуждаются всеми, кому не лень. Я сам автор нескольких учебных пособий и просто даю совет, что выпускать пособия лучше только в тех случаях, когда в них содержится материал, плохо описанный или вообще не описанный в учебной литературе. То есть материал, взятый из научных работ. То есть если кроме этих задач будут другие (сложные, и их будет больше), то все хорошо, а если нет — то… у нас один студент курсовую писал, он там штук 20-25 таких задач собрал. Значит его работа лучше вашей? Так не должно быть.

[@Zealint]

Но в последней после статьи Василевского, мне кажется, сложно сказать что-то новое. Собираюсь включить ДП по профилю только из соображений системности изложения.

Статья Василевского хороша тем, что там достаточно понятно разобраны те же самые тривиальные задачи. Причем других статей с подробным описанием я не видел. Но есть куча тонкостей, о которых он не пишет, а они возникают в задачах чуть более сложных, например, когда размерность больше игрушечной, или когда переход от профиля к профилю не такой простой. Кроме того, автор сильно хвалит изломанный профиль, но на примере одной задачи это выглядит крайне неубедительно. Например, эту задачу изломанным профилем решать нецелесообразно. При прочих равных условиях, обычный профиль экономит на порядок больше памяти, а при грамотном переходе оказывается ещё и быстрее. Кстати, это хорошая нетривиальная задача. Вот её другой вариант, посложнее.

[@shalex9154]

Я в своё время учил ДП по этому сайту Дистанционная подготовка, там много полезной теории для новичков, а главное есть задачи на которых ей можно проверить и проверочная система.

[@VeryWell]

Хорошо получилось в целом, но некоторые места я бы изменил. Может это из-за того что я вечером читаю, и голова не варит, но меня они озадачивали и приходилось перечитывать.

Например,

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

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

[@cybrid]

Согласен, ваша формулировка понятнее. Спасибо, приму к сведению.

[@just_vladimir]

А мы в свое время начинали изучение ДП с принципа оптимальности Беллмана, думаю стоит упомянуть о нем.

[@cybrid]

Да, наверно, стоит упомянуть о нем там, где идет формализация динамического программирования.

[@helions8]

В самом первом примере о числах Фибоначчи — первый и последний варианты дают разные ответы для одного n. Ну и рекурсивный алгоритм нарочиты выбран неоптимальным?

[@mihaild]

Неправда
misha@kihot:~/bred$ cat fib.c
#include <stdio.h>

int fib1(int n) {
if (n < 2) return 1;
else return fib1(n - 1) + fib1(n - 2);
}
int fib2(int n) {
int F[100], i;
F[0] = 1;
F[1] = 1;
for (i = 2; i <= n; i++) F[i] = F[i - 1] + F[i - 2];
return F[n];
}

int main(void) {
int i;
for (i = 0; i < 20; ++i) {
if (fib1(i) != fib2(i)) {
printf("PANIC!!! i=%d, fib1=%d, fib2=%d\n", i, fib1(i), fib2(i));
}
}
printf("Done\n");
return 0;
}
misha@kihot:~/bred$ gcc fib.c -o fib
misha@kihot:~/bred$ ./fib
Done


[@helions8]

Прежде чем минусовать, пожалуйста, сравните условия в вашем примере и в верху страницы.

[@cybrid]

Нет, был выбран самый очевидный алгоритм. Но я не вижу, в чем первый алгоритм является неоптимальным.

[@hx0]

Алгоритм про последовательность действительно не лучший, а может использоваться лишь как пример ДП.
Оптимальный алгоритм — использование формулы с золотым сечением:

#include <stdio.h>
#include <math.h>

const double mag = sqrt(5.0);
const double gold = (mag+1)/2;

int fibo(int n) {
    if (n == 2)
        return 1;
    return (pow(gold, n)-pow((1-gold), n))/mag;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", fibo(n));
    return 0;
}

[@mihaild]

Алгоритм с золотым сечением не очень хороший, т.к. для чисел с большим номером нужно вести вычисления с очень большой точностью.
Но можно сделать через матрицы.
Заметим, что
(F_{n+1}, F_n) = (F_n, F_{n-1})*A, где A = ((1,1),(1,0))
Значит, (F_{n+1}, F_n) = (F_1, F_0)*A^n.
Вычисляем A^n с помощью быстрого возведения в степень, и дальше все понятно.

[@Zealint]

Да, это называется «метод матрицы переноса» (Transfer Matrix Method), который известен уже как минимум 70 лет. Удивляет то, что его до сих пор не включают в стандартную универститетскую программу, а многие начинающие олимпиадники про него вообще не слышали.

[@Skiminok]

Начинающие стоящие олимпиадники — слышали все.
Более того, они даже понимают, что таким образом можно задать произвольное линейное рекуррентное отношение над произвольным кольцом.
Видел задачи, где быстрым возведением в степень решалась рекуррентность в Z₂.

[@cybrid]

Я такой алгоритм не рассматривал в силу того, что специфичен для чисел Фибоначчи. А я хотел проиллюстрировать общие идеи решения подобных задач.

[@helions8]

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

int fib(int a, int b, int lim) {
    return (lim <= 0) ? a : fib(b, a + b, lim - 1);
}

printf("%i\n", fib(0, 1, 40));

Да, он корявенький, но он работает и работает со скоростью вашего последнего, оптимального решения — порядка 0.002 sec судя по time — для вычисления n-го числа. Конечно же, можно добавить и хранение промежуточных результатов и т.д.

[@cybrid]

Скорее все варианты дают ответы со смещением относительно постановки задачи. Наверно, логичнее всего в постановке начать с F₀.

[@phpnewbie]

Интересный материал!

А учебное пособие для чего создается? Методичка для ВУЗа/школы? Будет ли публиковаться в электронном виде?

Есть ли вообще какая нибудь литература по спортивному программированию на русском языке?

[@cybrid]

Да, в первую очередь это методичка для ВУЗа. В полном виде, скорее всего, выставлено не будет. Предварительно я планировал выставить несколько наиболее интересных/сложных, на мой взгляд, параграфов в виде топиков и, возможно, в pdf.

Есть, например, Окулов «Программирование в алгоритмах», Меньшиков «Олимпиадные задачи по программированию». Большая часть тех книг по спортивному программированию, которые я читал, ориентирована в первую очередь на школьников.
Также отдельные разделы есть в классических книгах, посвященным алгоритмам.

[@vgrichina]

А я вот не могу понять, зачем напрягаются с динамическом программированием, когда есть мемоизация?

Вычислительная сложность та же в итоге, но не рушится изначальная абстракция функциями.

[@cybrid]

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

Во-вторых, при использовании мемоизации может получиться очень большая глубина вызовов.

Не могу придумать, как реализовать динамическое программирование по профилю с помощью мемоизации.

[@vgrichina]

Я как раз о том что вариант с мемоизацией гораздо ближе к исходным реккурентным соотношениям.

Ну а насчет глубины вызова – это как правило уже не проблема. Языки высокого уровня существуют для того чтоб уходить от технических тонкостей вроде этой.

Не знаком с сутью динамического программирования по профилю, по-этому не скажу тут ничего.

[@Skiminok]

> Не могу придумать, как реализовать динамическое программирование по профилю с помощью мемоизации.
Легко. Вот, например

[@MaximKat]

ДП очень похоже на мемоизацию. Два главных преимущества:
1. Итерация вместо рекурсии: не надо беспокоиться о стеке.
2. Мемоизация решает задачи «сверху вниз», а ДП — «снизу вверх». ДП экономит память за счет того, что можно выкидывать решения подзадач, которые больше не понадобятся: если подзадача (m,n) зависит только от (m-1,n-1) и (m-1,n), то для вычисления (5,1)...(5,5) нужны только (4,1)...(4,5), все предыдущие значения хранить не надо.

Мемоизация более интуитивная чем ДП, поэтому я обычно решаю задачи так:
1. Рекурсивное решение.
2. Добавляем мемоизацию.
3. Рисуем картинку с порядком вычислений:

4. Выделяем «уровни», чтобы следующий уровень зависел только от предыдущего. В этом примере уровнем может быть строчка или столбец таблицы.
5. ???
6. ДП!!!

[@vgrichina]

Ну то что ДП похоже на мемоизацию я не спорю )

Пока я понял только одно – ДП имеет смысл использовать лишь на очень заниженном размере стека и кучи, так как в другом случае проблем не возникает. Плюс в практических задачах обычно нет смысла выкидывать значения которые не нужны на данном этапе, так как они могут пригодится при следующем вызове функции.

[@MaximKat]

Грубо говоря да, ДП по сравнению с мемоизацией выигрывает только в объеме памяти.

Но говорить про «очень заниженный размер стека и кучи» нельзя: по такой же логике выходит, что мемоизацию имеет смысл использовать лишь на очень медленном компьютере :)

[@vgrichina]

Стек / память при мемоизации не растут экспоненциально как в случае с наивной реализацией, по-этому сравнение не корректно.

[@MaximKat]

Экспоненциально-не экспоненциально, но разница между O(n^2) и O(n), например, может быть существенна даже при нормальном количестве памяти. Но это уже от конкретной задачи все зависит, да.

[@Skiminok]

Интересно. Всю жизнь называл динамику по таблице — динамикой «снизу вверх», а то, что вы называете рекурсией с мемоизацией — динамикой «сверху вниз». Вроде так и в литературе обычно упоминается.
Т.е. мемоизация не «похожа» на ДП, она обычно, считается, и есть ДП.
В то же рекурсия без мемоизации (никому нахрен не нужная, ясен пень) — тоже, формально говоря, ДП «сверху вниз».

[@MaximKat]

Ну это уже чисто семантические тонкости. Вряд ли кто-то станет называть рекурсивное вычисление факториала — ДП :)

[@Skiminok]

Гм. Я буду называть. Ибо формально оно таки подпадает под определение ДП :)

[@MaximKat]

Формально что угодно попадает под определение ДП, правда подзадач — 0 штук :)

[@srez]

Я вот далек от олимпиадного программирования и меня всегда волновал вопрос, чем динамическое программирование отличается от банальной рекурсии с кэшированием?

[@MaximKat]

См. выше

[@AlexRussian]

вопрос к автору: почему в задаче номер 5 для подстроки AСCB стоит 3?
Как я понимаю должно быть 2.

[@cybrid]

Согласен, там закралась ошибка, должно быть 2.

[@igor_kleiner]

К сожалению много ляпов и неточностей:

«имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи» — некоторых, практически, такие неточные кванторы относят к задачам дин.прогр задачи решаемые другими способами.

«Приведенное решение является корректным и эффективным» — это решение не является эффективным, как и любое другое экспоненциальное решение.

«менно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все Fi для i < n), затем, зная решения подзадач» — нет нельзя такое решение назвать классическим. Это ваша додумка