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

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

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности


Классической задачей на последовательности является следующая.

Последовательность Фибоначчи Fn задается формулами: F1 = 1, F2 = 1,
Fn = Fn – 1 + Fn – 2 при n > 1. Необходимо найти Fn по номеру n.

Один из способов решения, который может показаться логичным и эффективным, — решение с помощью рекурсии:

int F(int n) {
 if (n < 2) return 1;
 else return F(n - 1) + F(n - 2);
}

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

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

int F(int n) {
 if (A[n] != -1) return A[n];
 if (n < 2) return 1;
 else {
  A[n] = F(n - 1) + F(n - 2);
  return A[n];
 }
}

Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

F[0] = 1;
F[1] = 1;
for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все Fi для i < n), затем, зная решения подзадач, нашли ответ (Fn = Fn – 1 + Fn – 2, Fn – 1 и Fn – 2 уже найдены).

Одномерное динамическое программирование


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

Пусть исходная задача заключается в нахождении некоторого числа T при исходных данных n1, n2, ..., nk. То есть мы можем говорить о функции T(n1, n2, ..., nk), значение которой и есть необходимый нам ответ. Тогда подзадачами будем считать задачи
T(i1, i2, ..., ik) при i1 < n1, i2 < n2, ..., ik < nk.

Далее мы будем о говорить об одномерном, двумерном и многомерном динамическом программировании при k = 1, k = 2, k > 2, соответственно.

Следующая задача одномерного динамического программирования встречается в различных вариациях.

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n < 32 полный перебор потребует нескольких секунд, а при n = 64 полный перебор не осуществим в принципе. Для решения задачи методом динамического программирования сведем исходную задачу к подзадачам.

При n = 1, n = 2 ответ очевиден. Допустим, что мы уже нашли Kn – 1, Kn – 2 — число таких последовательностей длины n – 1 и n – 2.

Посмотрим, какой может быть последовательность длины n. Если последний ее символ равен 0, то первые n – 1 — любая правильная последовательность длины
n – 1 (не важно, заканчивается она нулем или единицей — следом идет 0). Таких последовательностей всего Kn – 1. Если последний символ равен 1, то предпоследний символ обязательно должен быть равен 0 (иначе будет две единицы подряд), а первые
n – 2 символа — любая правильная последовательность длины n – 2, число таких последовательностей равно Kn – 2.



Таким образом, K1 = 2, K2 = 3, Kn = Kn – 1 + Kn – 2 при n > 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

Двумерное динамическое программирование


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

Приведем пару формулировок таких задач:

Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):



Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно
A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.



В каждую из уже пройденных клеток ведет ровно одна стрелка. Эта стрелка показывает, с какой стороны необходимо прийти в эту клетку, чтобы получить минимальный вес, записанный в клетке.

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

Задачи на подпоследовательности


Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1 <= i <= k – 1. Теперь можно найти L[k] следующим образом. Просматриваем все элементы A[i] для 1 <= i < k – 1. Если
A[i] < A[k], то k-ый элемент может стать продолжением подпоследовательности, окончившейся элементом A[i]. Длина полученной подпоследовательности будет на 1 больше L[i]. Чтобы найти L[k], необходимо перебрать все i от 1 до k – 1:
L[k] = max(L[i]) + 1, где максимум берется по всем i таким, что A[i] < A[k] и
1 <= i < k.

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

Чтобы восстановить саму подпоследовательность, можно для каждого элемента также сохранять номер предыдущего выбранного элемента, например, в массив N.

Рассмотрим решение этой задачи на примере последовательности 2, 8, 5, 9, 12, 6. Поскольку до 2 нет ни одного элемента, то максимальная подпоследовательность содержит только один элемент — L[1] = 1, а перед ним нет ни одного — N[1] = 0. Далее,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L[2] = 2, N[2] = 1.



Меньше A[3] = 5 только элемент A[1] = 2, поэтому 5 может стать продолжением только одной подпоследовательности — той, которая содержит 2. Тогда
L[3] = L[1] + 1 = 2, N[3] = 1, так как 2 стоит в позиции с номером 1. Аналогично выполняем еще три шага алгоритма и получаем окончательный результат.



Теперь выбираем максимальный элемент в массиве L и по массиву N восстанавливаем саму подпоследовательность 2, 5, 9, 12.

Еще одной классической задачей динамического программирования является задача о палиндромах.

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

Обозначим данную строку через S, а ее символы — через S[i], 1 <= i <= n. Будем рассматривать возможные подстроки данной строки с i-го по j-ый символ, обозначим их через S(i, j). Длины максимальных палиндромов для подстрок будем записывать в квадратный массив L: L[i][j] — длина максимального палиндрома, который можно получить из подстроки S(i, j).

Начнем решать задачу с самых простых подстрок. Для строки из одного символа (то есть подстроки вида S(i, i)) ответ очевиден — ничего вычеркивать не надо, такая строка будет палиндромом. Для строки из двух символов S(i, i + 1) возможны два варианта: если символы равны, то мы имеем палиндром, ничего вычеркивать не надо. Если же символы не равны, то вычеркиваем любой.

Пусть теперь нам дана подстрока S(i, j). Если первый (S[i]) и последний (S[j]) символы подстроки не совпадают, то один из них точно нужно вычеркнуть. Тогда у нас останется подстрока S(i, j – 1) или S(i + 1, j) — то есть мы сведем задачу к подзадаче: L[i][j] = max(L[i][j – 1], L[i + 1][j]). Если же первый и последний символы равны, то мы можем оставить оба, но необходимо знать решение задачи S(i + 1, j – 1):
L[i][j] = L[i + 1][j – 1] + 2.

Рассмотрим решение на примере строки ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подстрокам S(i, i) из одного символа. Затем начинаем рассматривать подстроки длины два. Во всех подстроках, кроме S(4, 5), символы различны, поэтому в соответствующие ячейки запишем 1, а в L[4][5] — 2.

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подстрок длины 3 получаются следующие значения: в подстроке ABA первая и последняя буквы равны, поэтому
L[1][3] = L[2][2] + 2. В остальных подстроках первая и последняя буквы различны.

BAC: L[2][4] = max(L[2][3], L[3][4]) = 1.
ACC: L[3][5] = max(L[3][4], L[4][5]) = 2.
CCB: L[4][6] = max(L[4][5], L[5][6]) = 2.
CBA: L[5][7] = max(L[5][6], L[6][7]) = 1.

Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке L[1][7] = 6 получим ответ.



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

Метки:
Поделиться публикацией
Похожие публикации
Комментарии 72
  • –5
    >> Задача 5. Дана строка из заглавных букв латинского алфавита. Необходимо найти длину наибольшего палиндрома, который можно получить вычеркиванием некоторых букв из данной строки.
    Где же вы раньше то были? =( У меня за решение такой задачи оригинальным методом за экзамен по программированию пять автоматом ставили…
    • +15
      Самому то додуматься не судьба конечно. Зато будете потом кичиться высшим образованием.
      • +1
        А Вы во время учебы самостоятельно додумывались до решения абсолютно всех задач? Позволю себе роскошь не поверить.
        • 0
          Да я лучший в группе. Все делал не только себе, но и другим всегда помогал. И ничего сложного в программе ВУЗов нет.
      • +2
        К сожалению, я сам не смог решить такую задачу, когда она мне попалась на олимпиаде. Вот сейчас пытаюсь систематизировать материал по ДП.
        • +2
          Такую задачу можно решить быстрее не за N^2 и без дополнительной памяти, а за NlogN, использую бинарный поиск + хеши ;) Если интересно могу написать решение.

          • 0
            Интересно, но хочется и самому сначала подумать :)
            • 0
              Если что, хорошая динамика в этой задаче работает за O(N) и с O(N) дополнительной памяти. Проверено на задаче с Тимуса.
              • 0
                Это как бы другая задача. Разницы не заметили?
                • 0
                  Спасибо, действительно другая, я топик по диагонали прочитал. По ссылке ищется длиннейший палиндром-подстрока, а в топике — палиндром-подпоследовательность. Для моего подхода это важно, так что вброс отменяется. :)
                  • 0
                    И какой у вас алгоритм для задачи с Тимуса?
                    • 0
                      По-моему, он известен только один классический (если я неправ, metar меня поправит и расскажет свой).
                      Вкратце: для каждого символа динамикой будем считать две величины — длину длиннейших нечетного и четного палиндрома с центром в данном символе. Тогда при линейном проходе можно смотреть, укладывается ли текущий символ в самый правый найденный доселе палиндром. Если нет — ищем втупую, если да — смотрим на уже вычисленное значение для симметричной буквы в «большом» (самом правом) палиндроме, обрезаем это число до границ большого, если надо, а дальше ищем втупую. Получается именно что O(N) времени (каждый проход втупую один раз затрагивает каждый символ при расширении вправо) и O(N) памяти (два массива).
            • 0
              Подумал, никаких идей. Так что буду благодарен, если вы напишете решение.
              • 0
                Могу подтолкнуть, вначале используя позиционный хеш, считаем его для всей строки за О(n). Потом простыми арифметическими манипуляциями можно получить его для любой подстроки за O(1). Делаем обход по строке и фиксируем центр палиндрома(стоит не забывать что длина палиндрома может быть чётной или нечётной), далее используя бинарный поиск ищем длину палиндрома(очевидно что если мы найдем палиндром длины 4, то не исключено что если добавить по 2 символа с обеих сторон, может получиться тоже палиндром).
                Если нужен код могу скинуть, но я не фанат такого ;)
                • 0
                  Ой, только что почитал выше топик и понял как я лажанул, это работает если палиндром подстрока а не подпоследовательность (
                  • 0
                    Равенство хэшей не гарантирует равенства строк. Поэтому либо нужен дополнительный проход для проверки строк (и сложность становится порядка N^2), либо вы утверждаете, что решаете задачу за O(N*logN) с некоторой вероятностью (может, даже большой, но отличной от 1).
              • 0
                Гм. С интересом послушаю.
                Решение за O(N log N) с бинпоиском и хэшами для длиннейшего палиндрома-подстроки знаю, для палиндрома-подпоследовательности — никогда не видел… Посидел немного, подумал — не получается же, не хватает информации, как ни крути, хэши работают с неразрываемыми подстроками символов.
                • 0
                  А, пока писал коммент, вы уже заметили ошибку :)
            • –35
              Хуйня
              • +2
                • –4
                  Блин всем сорри не сам коментил((( стоит оставить залогиненым акаунт(
                • 0
                  Настолько приелась эта тема, что аж тошно от ДП. Тем более, в период олимпиад)
                  В любом случае, классика неплохо разобрана.
                  • 0
                    Как мне показалось, сейчас на олимпиадах серьезного уровня есть тенденция ухода от ДП. По крайней мере от динамического программирования в чистом виде. Так что можете радоваться :)
                    • 0
                      Да? Во всяком случае, в школьных олимпиадах динамику пытаются сунуть туда, где она вообще не нужна.
                  • –1
                    >число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально
                    а что, простите, имеется в виду (я про «скоростью роста» ЧФ)?
                    • –1
                      Под скоростью роста я подразумевал соотношение Fn и n при увеличении n. Можно рассматривать Fn / n или, например, log Fn / n
                    • +2
                      Хорошо написано. Я давно уже не олимпиадник и нет времени следить за этим спортом, но с удовольствием бы прочел всю теорию из вашей книги. Просто чтобы быть «в тонусе».
                      • +6
                        Спасибо. В планах охватить основные разделы олимпиадного программирования. Первыми на очереди — динамическое программирование по профилю и геометрия.
                        • 0
                          Здорово, остальные главы из книги тоже будут опубликованы? Буду следить с интересом. Спасибо за хороший материал, вспомнил, как сам на олимпиадах участвовал.
                          • +1
                            Да, планирую продолжить публикацию. Не обещаю, что это будет быстро.
                      • +5
                        На вашем месте я бы не стал рассматривать тривиальные упражнения в учебном пособии. Эти задачи встречаются очень уж часто и слишком простые, чтобы показать реальную силу ДП. Например, возьмите задачу 4 и рассмотрите решение за O(n*log(n)), а не за O(n2), как сейчас. В последней задаче можно дополнительно написать, как вместо матрицы хранить только один массив (или хранить матрицу, но не заводить вторую для получения ответа). Это уже будет куда лучше.

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

                        Какие задачи включить в данный раздел? Ну, те же две кучи монет. Наибольшая возрастающая подпоследовательность за O(n*lon(n)). Динамику по профилю обязательно. Какую-нибудь динамику по подмножествам, например, точное решение задачи Коммивояжера. Вообще, можно брать все, что плохо или мало описано в других источниках. Если вы конечно не претендуете на монографию с полным обзором всех таких задач за последние 70 лет (метод матрицы переноса, он же динамика по профилю был известен ещё в 40-х годах, применялся для точного решения модели Изинга без воздействия внешнего поля).
                        • +1
                          Спасибо за подробный совет. Почему я включаю тривиальные задачи? Чтобы научиться решать сложные задачи, надо с чего-то начинать. На практике я для некоторых задач стараюсь дать несколько уровней сложности — чтобы, например, на первом уровне проходил алгоритм за O(n2), а на втором уже только за O(n * log(n)).
                          В планах задача о рюкзаке и динамика по профилю. Но в последней после статьи Василевского, мне кажется, сложно сказать что-то новое. Собираюсь включить ДП по профилю только из соображений системности изложения.
                          Про две кучи монет — спасибо. Как-то эта задача прошла мимо меня.
                          • +2
                            Что-то новое сказать в динамике по профилю элементарно. Василевский, к примеру, ни звуком не заикается о том, что понятие «профиль» — это произвольное состояние, характеризирующее множество битмаской, а не только всяческие строки и столбцы в двумерном массиве. Видел пару человек, которые начитались Василевского, потом сталкивались с динамикой по состояниям, и у них немного сносило мозг и рвало шаблон: «А где же тут таблица-то?»

                            На Топкодере в 500 Div 1 очень любят часто динамику по состояниям. К примеру, Gifts.
                            • 0
                              Посоветуйте, где лучше ето все таки разобрать (динамика по [изломаному] профилю). Или кикую-то литературу по етому делу.
                            • 0
                              Чтобы научиться решать сложные задачи, надо с чего-то начинать.

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

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

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

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

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

                                такая очевидная мысль в такой перегруженной форме озадачивает и заставляет уделить ей дополнительное, лишнее внимание.
                                >>Для подобных задач характерно то, что каждый отдельный маршрут не может пройти более одного раза по одной и той же клетке.
                                • 0
                                  Согласен, ваша формулировка понятнее. Спасибо, приму к сведению.
                                • +2
                                  А мы в свое время начинали изучение ДП с принципа оптимальности Беллмана, думаю стоит упомянуть о нем.
                                  • 0
                                    Да, наверно, стоит упомянуть о нем там, где идет формализация динамического программирования.
                                  • –2
                                    В самом первом примере о числах Фибоначчи — первый и последний варианты дают разные ответы для одного n. Ну и рекурсивный алгоритм нарочиты выбран неоптимальным?
                                    • 0
                                      Неправда
                                      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
                                      • 0
                                        Прежде чем минусовать, пожалуйста, сравните условия в вашем примере и в верху страницы.
                                      • 0
                                        Нет, был выбран самый очевидный алгоритм. Но я не вижу, в чем первый алгоритм является неоптимальным.
                                        • 0
                                          Алгоритм про последовательность действительно не лучший, а может использоваться лишь как пример ДП.
                                          Оптимальный алгоритм — использование формулы с золотым сечением:

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


                                          • +6
                                            Алгоритм с золотым сечением не очень хороший, т.к. для чисел с большим номером нужно вести вычисления с очень большой точностью.
                                            Но можно сделать через матрицы.
                                            Заметим, что
                                            (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 с помощью быстрого возведения в степень, и дальше все понятно.
                                            • +2
                                              Да, это называется «метод матрицы переноса» (Transfer Matrix Method), который известен уже как минимум 70 лет. Удивляет то, что его до сих пор не включают в стандартную универститетскую программу, а многие начинающие олимпиадники про него вообще не слышали.
                                              • 0
                                                Начинающие стоящие олимпиадники — слышали все.
                                                Более того, они даже понимают, что таким образом можно задать произвольное линейное рекуррентное отношение над произвольным кольцом.
                                                Видел задачи, где быстрым возведением в степень решалась рекуррентность в Z2.
                                            • 0
                                              Я такой алгоритм не рассматривал в силу того, что специфичен для чисел Фибоначчи. А я хотел проиллюстрировать общие идеи решения подобных задач.
                                            • 0
                                              Да, этот пример с рекурсией самый часто встречающийся, но он очень неоптимальный. Кроме того, чтобы вычислять 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-го числа. Конечно же, можно добавить и хранение промежуточных результатов и т.д.
                                            • 0
                                              Скорее все варианты дают ответы со смещением относительно постановки задачи. Наверно, логичнее всего в постановке начать с F0.
                                            • 0
                                              Интересный материал!

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

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

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

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

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

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

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

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

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

                                                      Мемоизация более интуитивная чем ДП, поэтому я обычно решаю задачи так:
                                                      1. Рекурсивное решение.
                                                      2. Добавляем мемоизацию.
                                                      3. Рисуем картинку с порядком вычислений:
                                                      image
                                                      4. Выделяем «уровни», чтобы следующий уровень зависел только от предыдущего. В этом примере уровнем может быть строчка или столбец таблицы.
                                                      5. ???
                                                      6. ДП!!!
                                                      • 0
                                                        Ну то что ДП похоже на мемоизацию я не спорю )

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

                                                          Но говорить про «очень заниженный размер стека и кучи» нельзя: по такой же логике выходит, что мемоизацию имеет смысл использовать лишь на очень медленном компьютере :)
                                                          • 0
                                                            Стек / память при мемоизации не растут экспоненциально как в случае с наивной реализацией, по-этому сравнение не корректно.
                                                            • 0
                                                              Экспоненциально-не экспоненциально, но разница между O(n^2) и O(n), например, может быть существенна даже при нормальном количестве памяти. Но это уже от конкретной задачи все зависит, да.
                                                        • 0
                                                          Интересно. Всю жизнь называл динамику по таблице — динамикой «снизу вверх», а то, что вы называете рекурсией с мемоизацией — динамикой «сверху вниз». Вроде так и в литературе обычно упоминается.
                                                          Т.е. мемоизация не «похожа» на ДП, она обычно, считается, и есть ДП.
                                                          В то же рекурсия без мемоизации (никому нахрен не нужная, ясен пень) — тоже, формально говоря, ДП «сверху вниз».
                                                          • 0
                                                            Ну это уже чисто семантические тонкости. Вряд ли кто-то станет называть рекурсивное вычисление факториала — ДП :)
                                                            • 0
                                                              Гм. Я буду называть. Ибо формально оно таки подпадает под определение ДП :)
                                                              • +1
                                                                Формально что угодно попадает под определение ДП, правда подзадач — 0 штук :)
                                                      • 0
                                                        Я вот далек от олимпиадного программирования и меня всегда волновал вопрос, чем динамическое программирование отличается от банальной рекурсии с кэшированием?
                                                      • +1
                                                        вопрос к автору: почему в задаче номер 5 для подстроки AСCB стоит 3?
                                                        Как я понимаю должно быть 2.
                                                        • 0
                                                          Согласен, там закралась ошибка, должно быть 2.
                                                        • 0
                                                          К сожалению много ляпов и неточностей:

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

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

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

                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.