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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
(не показана 41 промежуточная версия этого же участника)
Строка 3: Строка 3:
=== Числа Фибоначчи ===
=== Числа Фибоначчи ===


Найти n-ый элемент ряда Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21...
Найти n-й элемент ряда Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21...


Вид подзадачи: d[i] — i-ое число Фибоначчи.
Вид подзадачи: d[i] — i-е число Фибоначчи.


Рекуррентная формула: d[i] = d[i - 1] + d[i - 2].
Рекуррентная формула: d[i] = d[i - 1] + d[i - 2].
Строка 13: Строка 13:
Вид ответа: d[n]. Сложность O(N). (*Данная задача может быть решена за O(logN).)
Вид ответа: d[n]. Сложность O(N). (*Данная задача может быть решена за O(logN).)


=== Задача о рюкзаке с повторениями ===
* [http://brilliant.org/wiki/fast-fibonacci-transform/ Brilliant.org — Fast Fibonacci Transform]
 
=== Рюкзак: количество способов набрать вес M, предметы можно брать несколько раз ===
* [https://cses.fi/problemset/task/1635 CSES 1635]
 
=== Рюкзак: набрать вес <= M, максимизировать стоимость, предметы можно брать несколько раз ===


Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. Каждый предмет можно брать неограниченное число раз.
Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. Каждый предмет можно брать неограниченное число раз.
Строка 24: Строка 29:


Вид ответа: d[m]. Сложность O(N &times; M).
Вид ответа: d[m]. Сложность O(N &times; M).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_0.swf Dean B. &mdash; Integer knapsack problem]
=== Размен минимальным количеством монет ===
Дано N монет, i-я из которых имеет целочисленную стоимость p[i] > 0. Определить минимальное количество монет, которыми можно разменять сумму M.
Вид подзадачи: d[j] &mdash; минимальное количество монет общей стоимостью j.
Рекуррентная формула: d[j] = min(d[j - p[i]] + 1), где i &isin; 0..(n - 1).
База рекурсии: Если j = 0, то d[j] = 0; если j < 0, то d[j] = INF.
Вид ответа: d[m]. Сложность O(N &times; M).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_2.swf Dean B. &mdash; Making Change]
* [https://cses.fi/problemset/task/1634 CSES 1634]
=== Другие задачи ===
* [http://acm.timus.ru/problem.aspx?num=1087 Timus #1087 &mdash; Время забирать камни]
* [https://cses.fi/problemset/task/1140 CSES 1140]
* [https://cses.fi/problemset/task/1633 CSES 1633]
* [https://cses.fi/problemset/task/1637 CSES 1637]


== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс) ==
== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс) ==
Строка 51: Строка 80:
Вид ответа: d[n]. Сложность O(N).
Вид ответа: d[n]. Сложность O(N).


== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс + привязка) ==
* [http://codeforces.ru/gym/100070/problem/K Codeforces #100070.K &mdash; Лесенка]
 
== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс; модификация) ==


=== Подотрезок с максимальной суммой ===
=== Подотрезок с максимальной суммой ===
Строка 64: Строка 95:


Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N).
Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_1.swf Dean B. &mdash; Maximum Value Contiguous Subsequence]
* [[ACMP 1092]]
* [http://acm.timus.ru/problem.aspx?num=1296 Timus #1296 &mdash; Гиперпереход]


=== Наибольшая возрастающая подпоследовательность (LIS) ===
=== Наибольшая возрастающая подпоследовательность (LIS) ===
Строка 77: Строка 112:
Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N<sup>2</sup>).
Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N<sup>2</sup>).


* [http://acmp.ru/index.asp?main=task&id_task=122 ACMP #122 &mdash; Максимальная подпоследовательность]
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_3.swf Dean B. &mdash; Longest Increasing Subsequence]
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_6.swf Dean B. &mdash; Building Bridges]
* [[ACMP 122]]
* [http://codeforces.ru/gym/100082/problem/A Codeforces #100082.A &mdash; Наибольшая возрастающая подпоследовательность]
 
(*Данная задача может быть решена за O(NlogN))
* [[ACMP 1464]]
* [https://cses.fi/problemset/task/1145 CSES 1145]
* [https://open.kattis.com/problems/longincsubseq Kattis longincsubseq] ([https://github.com/vfolunin/archives-solutions/blob/master/Kattis/longincsubseq.cpp решение: лексикографически минимальная LIS с сертификатом, O(NlogN)])
* [https://open.kattis.com/problems/increasingsubsequence Kattis increasingsubsequence]
 
{|width=100%
|width=50%|
int getLisSize(vector<int> &a) {
    vector<int> lisSize(a.size(), 1);
    for (int i = 1; i < a.size(); i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && lisSize[i] < lisSize[j] + 1)
                lisSize[i] = lisSize[j] + 1;
    return *max_element(lisSize.begin(), lisSize.end());
}
|width=50%|
int getLisSize(vector<int> &a) {
    vector<int> lisLast(a.size() + 1, 1e9);
    lisLast[0] = -1e9;
   
    for (int value : a)
        *lower_bound(lisLast.begin(), lisLast.end(), value) = value;
    int lisSize = a.size();
    while (lisLast[lisSize] == 1e9)
        lisSize--;
    return lisSize;
}
|-
|width=50%|
vector<int> getLis(vector<int> &a) {
    vector<int> lisSize(a.size(), 1);
    vector<int> from(a.size(), -1);
    for (int i = 1; i < a.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && lisSize[i] < lisSize[j] + 1) {
                lisSize[i] = lisSize[j] + 1;
                from[i] = j;
            }
        }
    }
    vector<int> lis;
    for (int i = max_element(lisSize.begin(), lisSize.end()) - lisSize.begin(); i != -1; i = from[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());
    return lis;
}
|width=50%|
vector<int> getLis(vector<int> &a) {
    vector<int> lisLast(a.size() + 1, 1e9);
    lisLast[0] = -1e9;
    vector<int> lisLastIndex(a.size() + 1, -1);
    vector<int> from(a.size(), -1);
    for (int i = 0; i < a.size(); i++) {
        int lisSize = lower_bound(lisLast.begin(), lisLast.end(), a[i]) - lisLast.begin();
        lisLast[lisSize] = a[i];
        lisLastIndex[lisSize] = i;
        from[i] = lisLastIndex[lisSize - 1];
    }
    int lisSize = a.size();
    while (lisLast[lisSize] == 1e9)
        lisSize--;
    vector<int> lis;
    for (int i = lisLastIndex[lisSize]; i != -1; i = from[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());
    return lis;
}
|}


=== Наибольшая последовательность вкладываемых параллелепипедов ===
=== Наибольшая последовательность вкладываемых параллелепипедов ===
Строка 90: Строка 214:


Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N<sup>2</sup>).
Вид ответа: max(d[i]), где i &isin; 0..(n - 1). Сложность O(N<sup>2</sup>).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_5.swf Dean B. &mdash; Box Stacking]
== Двумерная динамика (вход &mdash; два параметра; подзадача &mdash; два меньших параметра) ==
=== Биномиальные коэффициенты ===
Вычислить C(m, n) &mdash; количество способов выбрать m предметов из n.
Вид подзадачи: d[i][j] &mdash; количество способов выбрать j предметов из i.
Рекуррентная формула: d[i][j] = d[i - 1][j] + d[i - 1][j - 1].
База рекурсии: Если j = 1 или j = i, то d[i][j] = 1.
Вид ответа: d[n][m]. Сложность O(N &times; M).
=== Бросание шариков ===
Есть N-этажное здание и M шариков. Шарики можно бросать с разных этажей; начиная с некоторого этажа X и выше шарики при броске разбиваются. Требуется определить этаж X за наименьшее число бросков. Разбитый шарик нельзя бросать снова (количество шариков уменьшается), целый — можно.
Вид подзадачи: d[i][j] — минимальное количество бросков для определения одного из i этажей, если есть j шариков.
Рекуррентная формула: d[i][j] = 1 + min(max(d[k - 1][j - 1], d[n - k][j])), где k = 1..i.
База рекурсии: Если i = 0, то d[i][j] = 0. Если j = 1, то d[i][j] = i (придётся бросать снизу вверх подряд).
Вид ответа: d[n][m]. Сложность O(N<sup>2</sup> &times; M) (*Можно быстрее).
* [http://brilliant.org/wiki/egg-dropping/ Brilliant.org — Egg dropping]
* [https://informatics.msk.ru/mod/statements/view.php?chapterid=3815#1 MCCME 3815]
=== Другие задачи ===
* [https://acmp.ru/index.asp?main=task&id_task=16 ACMP 16]
* [https://cses.fi/problemset/task/1744 CSES 1744]
* [https://cses.fi/problemset/task/1746 CSES 1746]


== Двумерная динамика (вход &mdash; параметр, последовательность; подзадача &mdash; меньший параметр, префикс) ==
== Двумерная динамика (вход &mdash; параметр, последовательность; подзадача &mdash; меньший параметр, префикс) ==


=== Задача о рюкзаке без повторений ===
=== Рюкзак: можем ли набрать вес M ===
* [https://cses.fi/problemset/task/1745 CSES 1745]
 
=== Рюкзак: набрать вес <= M, максимизировать стоимость ===


Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна.
Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна.
Строка 105: Строка 268:
Вид ответа: d[n][m]. Сложность O(N &times; M).
Вид ответа: d[n][m]. Сложность O(N &times; M).


=== Задача о рюкзаке с ограниченными повторениями ===
* [http://brilliant.org/wiki/backpack-problem/ Brilliant.org — Backpack Problem]
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_7.swf Dean B. &mdash; Integer Knapsack Problem (Duplicate Items Forbidden)]
* [https://cses.fi/problemset/task/1158 CSES 1158]
 
=== Рюкзак: набрать вес <= M, максимизировать стоимость, предметы можно брать не более K раз ===


Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. i-й предмет можно брать k[i] раз.
Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. i-й предмет можно брать k[i] раз.
Строка 117: Строка 284:
Вид ответа: d[n][m]. Сложность O(N &times; M<sup>2</sup>).
Вид ответа: d[n][m]. Сложность O(N &times; M<sup>2</sup>).


=== Восстановление скобок ===
=== Рюкзак: разделить на две кучи близкого веса ===
 
Дано N камней, i-й из которых имеет целочисленный вес 0 < w[i] <= M. Разделить камни на две кучи как можно более близкого веса, вывести разность весов куч.
 
Вид подзадачи: d[i][j] &mdash; 1, если можно набрать кучу веса j из подмножества камней от 0-го до (i - 1)-го, или 0 в противном случае.
 
Рекуррентная формула: d[i][j] = d[i - 1][j - w[i]].
 
База рекурсии: d[0][0] = 1.
 
Вид ответа: min(|j - (&sum;w - j)|), где d[n][j] = 1. Сложность O(N<sup>2</sup> &times; M).
 
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_4.swf Dean B. &mdash; Balanced Partition]
* [https://cses.fi/problemset/task/1093 CSES 1093]
 
=== Число способов восстановления скобок заменой ===


Дана строка S, состоящая из символов '(', ')' и '?'. Найти количество способов заменить знаки вопроса на скобки так, чтобы получилась правильная скобочная последовательность.
Дана строка S, состоящая из символов '(', ')' и '?'. Найти количество способов заменить знаки вопроса на скобки так, чтобы получилась правильная скобочная последовательность.
Строка 130: Строка 312:


* [http://acmp.ru/index.asp?main=task&id_task=123 ACMP #123 &mdash; Восстановление скобок]
* [http://acmp.ru/index.asp?main=task&id_task=123 ACMP #123 &mdash; Восстановление скобок]
=== Другие задачи ===
* [https://cses.fi/problemset/task/1636 CSES 1636]


== Двумерная динамика (вход &mdash; последовательность; подзадача &mdash; подотрезок) ==
== Двумерная динамика (вход &mdash; последовательность; подзадача &mdash; подотрезок) ==
Строка 160: Строка 345:


* [http://acmp.ru/index.asp?main=task&id_task=481 ACMP #481 &mdash; Количество палиндромов]
* [http://acmp.ru/index.asp?main=task&id_task=481 ACMP #481 &mdash; Количество палиндромов]
* [http://acmp.ru/index.asp?main=task&id_task=1328 ACMP #1328 &mdash; Палиндромы]


=== Восстановление скобочного выражения ===
=== Число действий для восстановления скобок вставкой ===


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


Вид подзадачи: d[i][j] &mdash; минимальное количество символов, которые требуется добавить в подстроку S[i..j], чтобы она стала правильным скобочным выражением.
Вид подзадачи: d[i][j] &mdash; минимальное количество символов, которые требуется добавить в подстроку S[i..j], чтобы получилась правильная скобочная последовательность.


Рекуррентная формула: d[i][j] = min(d[i][k] + d[k + 1][j]), где k &isin; i..(j - 1); если S[i] и S[j] &mdash; соответствующие открывающая и закрывающая скобки, то d[i][j] = min(d[i][j], d[i + 1][j - 1]).
Рекуррентная формула: d[i][j] = min(d[i][k] + d[k + 1][j]), где k &isin; i..(j - 1); если S[i] и S[j] &mdash; соответствующие открывающая и закрывающая скобки, то d[i][j] = min(d[i][j], d[i + 1][j - 1]).
Строка 174: Строка 360:


* [http://acmp.ru/index.asp?main=task&id_task=249 ACMP #249 &mdash; Скобки]
* [http://acmp.ru/index.asp?main=task&id_task=249 ACMP #249 &mdash; Скобки]
* [http://acmp.ru/index.asp?main=task&id_task=1340 ACMP #1340 &mdash; Скобки (3)]
=== Игра со стиранием концов ленты ===
Есть лента A[], на которой записано N чисел. Два игрока поочерёдно стирают с ленты первое или последнее число и добавляют его к своей сумме. Какую максимальную сумму может получить первый игрок?
Вид подзадачи: d[i][j] &mdash; максимальная сумма, которую может набрать начинающий игрок на подотрезке ленты [i..j].
Рекуррентная формула: d[i][j] = max(A[i] + &sum;<sub>A</sub>((i + 1)..j) - d[i + 1][j], A[j] + &sum;<sub>A</sub>(i..(j - 1)) - d[i][j - 1]).
База рекурсии: d[i][i] = A[i].
Вид ответа: d[0][n - 1]. Сложность O(N<sup>2</sup>).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_10.swf Dean B. &mdash; Optimal Strategy for a Game]
* [https://cses.fi/problemset/task/1097 CSES 1097]


== Двумерная динамика (вход &mdash; две последовательности; подзадача &mdash; два префикса) ==
== Двумерная динамика (вход &mdash; две последовательности; подзадача &mdash; два префикса) ==
=== Редакционное расстояние ===
Дана строка A длины N и строка B длины M. Вставка символа стоит C<sub>i</sub>, удаление &mdash; C<sub>d</sub>, замена &mdash; C<sub>r</sub>. Найти минимальную стоимость получения строки B из строки A.
Вид подзадачи: d[i][j] &mdash; минимальная стоимость получения префикса B[0..(j - 1)] из префикса A[0..(i - 1)].
Рекуррентная формула: d[i][j] = min(d[i][j - 1] + C<sub>i</sub>, d[i - 1][j] + C<sub>d</sub>, d[i - 1][j - 1] + X), где X = C<sub>r</sub>, если A[i - 1] &ne; B[j - 1], иначе X = 0.
База рекурсии: d[0][0] = 0.
Вид ответа: d[n][m]. Сложность O(N &times; M).
* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_8.swf Dean B. &mdash; Edit Distance]
* [https://cses.fi/problemset/task/1639 CSES 1639]
=== Наибольшая общая подпоследовательность (LCS) ===
Дана строка A длины N и строка B длины M. Найти длину их наибольшей общей подпоследовательности.
Вид подзадачи: d[i][j] &mdash; длина наибольшей общей подпоследовательности префиксов A[0..(i - 1)] и B[0..(j - 1)].
Рекуррентная формула: Если A[i - 1] = B[j - 1], то d[i][j] = d[i - 1][j - 1] + 1, иначе d[i][j] = max(d[i - 1][j], d[i][j - 1]).
База рекурсии: d[0][0] = 0.
Вид ответа: d[n][m]. Сложность O(N &times; M).


=== Соответствие строки шаблону ===
=== Соответствие строки шаблону ===
Строка 189: Строка 418:
Вид ответа: d[n][m]. Сложность O(N<sup>2</sup> &times; M).
Вид ответа: d[n][m]. Сложность O(N<sup>2</sup> &times; M).


* [http://acmp.ru/index.asp?main=task&id_task=104 ACMP #104 &mdash; Шаблон]
* [https://acmp.ru/index.asp?main=task&id_task=104 ACMP 104]
* [https://informatics.msk.ru/mod/statements/view.php?chapterid=3819 MCCME 3819]
* [https://informatics.msk.ru/mod/statements/view.php?chapterid=112626 MCCME 112626]
 
== Двумерная динамика (вход &mdash; две последовательности; подзадача &mdash; два префикса; модификация) ==
 
=== Наибольшая общая подстрока ===
 
Дана строка A длины N и строка B длины M. Найти длину их наибольшей общей подстроки.
 
Вид подзадачи: d[i][j] &mdash; длина наибольшей общей подстроки префиксов A[0..(i - 1)] и B[0..(j - 1)], заканчивающейся в них на позициях (i - 1) и (j - 1) соответственно.
 
Рекуррентная формула: Если A[i - 1] = B[j - 1], то d[i][j] = d[i - 1][j - 1] + 1, иначе d[i][j] = 0.
 
База рекурсии: d[0][0] = 0.
 
Вид ответа: max(d[i][j]), i &isin; 1..N. j &isin; 1..M. Сложность O(N &times; M).


== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс) ==
== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс) ==
Строка 204: Строка 449:


Вид ответа: d[n][m]. Сложность O(N &times; M).
Вид ответа: d[n][m]. Сложность O(N &times; M).
* [https://cses.fi/problemset/task/1638 CSES 1638]


=== Максимальный путь в таблице ===
=== Максимальный путь в таблице ===
Строка 218: Строка 465:


* [http://acmp.ru/index.asp?main=task&id_task=120 ACMP #120 &mdash; Минимальный путь в таблице]
* [http://acmp.ru/index.asp?main=task&id_task=120 ACMP #120 &mdash; Минимальный путь в таблице]
* [http://acm.timus.ru/problem.aspx?num=1119 Timus #1119 &mdash; Метро]


== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс + привязка) ==
== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс; модификация) ==


=== Максимальный квадрат из единиц ===
=== Максимальный квадрат из единиц ===
Строка 227: Строка 475:
Вид подзадачи: d[i][j] &mdash; сторона максимального единичного квадрата с правым нижним углом в клетке [i, j].
Вид подзадачи: d[i][j] &mdash; сторона максимального единичного квадрата с правым нижним углом в клетке [i, j].


Рекуррентная формула: d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i][j - 1]).
Рекуррентная формула: d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]).


База рекурсии: d[0][0] = a[0][0]; если a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0.
База рекурсии: d[0][0] = a[0][0]; если a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0.
Строка 233: Строка 481:
Вид ответа: max(d[i][j])<sup>2</sup>, где i &isin; 0..(n - 1), j &isin; 0..(m - 1). Сложность O(N &times; M).
Вид ответа: max(d[i][j])<sup>2</sup>, где i &isin; 0..(n - 1), j &isin; 0..(m - 1). Сложность O(N &times; M).


[[Категория:Учебный курс «Алгоритмы и структуры данных»]]
== Динамика на подмножествах ==
* [https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/ Hackerearth — Dynamic Programming and Bit Masking]
* [https://usaco.guide/plat/dp-bitmasks USACO Guide — Dynamic Programming on Bitmasks]
 
== Динамика на деревьях ==
 
=== Другие задачи ===
 
* [http://acm.timus.ru/problem.aspx?num=1018 Timus #1018 &mdash; Двоичная яблоня]
 
== Ссылки ==
* [http://brestprog.by/topics/dp/ brestprog — Динамическое программирование на примерах]
* [http://brestprog.by/topics/bitmasks/ brestprog — Битовые маски. Динамическое программирование по маскам]
* [http://algorithmica.org/tg/dp-basics algorithmica.org — Введение в динамическое программирование]
* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]
* [https://ejudge.lksh.ru/archive/2011/07/B/files/dp-profile.pdf Василевский Б. — Динамическое программирование по профилю]
* [https://notes.algoprog.ru/dynprog/index.html Калинин П. — Динамическое программирование]
* [https://ejudge.lksh.ru/archive/2014/07/Cprime/stuff/Dynamic_programming.pdf Кириенко Д. — Динамическое программирование]
* [http://www.youtube.com/watch?v=q_n2vzVNXE4&list=PLrS21S1jm43geDXVdeQy96P-f59pXeyPC&index=9 Маврин П. — Динамическое программирование]
* [http://codeforces.com/blog/entry/6221 Codeforces &mdash; ДП учимся видеть состояния, придумывать переход]
* [http://brilliant.org/wiki/problem-solving-dynamic-programming/ Brilliant.org — Dynamic Programming]
* [http://people.cs.clemson.edu/~bcdean/dp_practice people.cs.clemson.edu — Dynamic Programming Practice Problems]
 
[[Категория:Динамическое программирование]]

Текущая версия от 16:43, 18 июня 2023

Одномерная динамика (вход — параметр; подзадача — меньший параметр)

Числа Фибоначчи

Найти n-й элемент ряда Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21...

Вид подзадачи: d[i] — i-е число Фибоначчи.

Рекуррентная формула: d[i] = d[i - 1] + d[i - 2].

База рекурсии: d[0] = d[1] = 1.

Вид ответа: d[n]. Сложность O(N). (*Данная задача может быть решена за O(logN).)

Рюкзак: количество способов набрать вес M, предметы можно брать несколько раз

Рюкзак: набрать вес <= M, максимизировать стоимость, предметы можно брать несколько раз

Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. Каждый предмет можно брать неограниченное число раз.

Вид подзадачи: d[j] — максимальная стоимость подмножества предметов, общий вес которых не превосходит j.

Рекуррентная формула: d[j] = max(d[j - w[i]] + p[i]), где i ∈ 0..(n - 1).

База рекурсии: Если j <= 0, то d[j] = 0.

Вид ответа: d[m]. Сложность O(N × M).

Размен минимальным количеством монет

Дано N монет, i-я из которых имеет целочисленную стоимость p[i] > 0. Определить минимальное количество монет, которыми можно разменять сумму M.

Вид подзадачи: d[j] — минимальное количество монет общей стоимостью j.

Рекуррентная формула: d[j] = min(d[j - p[i]] + 1), где i ∈ 0..(n - 1).

База рекурсии: Если j = 0, то d[j] = 0; если j < 0, то d[j] = INF.

Вид ответа: d[m]. Сложность O(N × M).

Другие задачи

Одномерная динамика (вход — последовательность; подзадача — префикс)

Количество путей в полосе

Дана полоса из n клеток. Фишка находится в клетке 0 и может перемещаться на 1, 2 или 3 клетки вправо. Найти количество различных путей фишки от клетки 0 до клетки (n - 1). Некоторые клетки могут быть непроходимыми.

Вид подзадачи: d[i] — количество путей из клетки 0 в клетку i.

Рекуррентная формула: d[i] = d[i - 1] + d[i - 2] + d[i - 3].

База рекурсии: d[0] = 1; если i-я клетка непроходимая или i < 0, то d[i] = 0.

Вид ответа: d[n]. Сложность O(N).

Максимальный путь в полосе

Дана полоса из n клеток, в каждой клетке которой записано число. Фишка находится в клетке 0 и может перемещаться на 1, 2 или 3 клетки вправо. Найти максимально возможную сумму чисел на посещённых клетках при перемещении фишки от клетки 0 до клетки (n - 1). Некоторые клетки могут быть непроходимыми.

Вид подзадачи: d[i] — максимальная сумма на пути из клетки 0 в клетку i.

Рекуррентная формула: d[i] = a[i] + max(d[i - 1], d[i - 2], d[i - 3]).

База рекурсии: d[0] = a[0]; если i-я клетка непроходимая или i < 0, то d[i] = -INF.

Вид ответа: d[n]. Сложность O(N).

Одномерная динамика (вход — последовательность; подзадача — префикс; модификация)

Подотрезок с максимальной суммой

Дан целочисленный массив a[n]. Определить максимальную сумму его элементов, принадлежащих некоторому непрерывному диапазону a[i]..a[j].

Вид подзадачи: d[i] — максимальная сумма на отрезке, заканчивающимся на элементе a[i].

Рекуррентная формула: d[i] = max(d[i - 1] + a[i], a[i]).

База рекурсии: d[0] = a[0].

Вид ответа: max(d[i]), где i ∈ 0..(n - 1). Сложность O(N).

Наибольшая возрастающая подпоследовательность (LIS)

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

Вид подзадачи: d[i] — максимальная длина возрастающей подпоследовательности, заканчивающейся на элементе a[i].

Рекуррентная формула: d[i] = 1 + max(d[j]), где j = 0..(i - 1) и a[j] < a[i].

База рекурсии: d[0] = 1.

Вид ответа: max(d[i]), где i ∈ 0..(n - 1). Сложность O(N2).

(*Данная задача может быть решена за O(NlogN))

int getLisSize(vector<int> &a) {
    vector<int> lisSize(a.size(), 1);

    for (int i = 1; i < a.size(); i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && lisSize[i] < lisSize[j] + 1)
                lisSize[i] = lisSize[j] + 1;

    return *max_element(lisSize.begin(), lisSize.end());
}


int getLisSize(vector<int> &a) {
    vector<int> lisLast(a.size() + 1, 1e9);
    lisLast[0] = -1e9;
    
    for (int value : a)
        *lower_bound(lisLast.begin(), lisLast.end(), value) = value;

    int lisSize = a.size();
    while (lisLast[lisSize] == 1e9)
        lisSize--;
    return lisSize;
}
vector<int> getLis(vector<int> &a) {
    vector<int> lisSize(a.size(), 1);
    vector<int> from(a.size(), -1);

    for (int i = 1; i < a.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && lisSize[i] < lisSize[j] + 1) {
                lisSize[i] = lisSize[j] + 1;
                from[i] = j;
            }
        }
    }

    vector<int> lis;
    for (int i = max_element(lisSize.begin(), lisSize.end()) - lisSize.begin(); i != -1; i = from[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());

    return lis;
}




vector<int> getLis(vector<int> &a) {
    vector<int> lisLast(a.size() + 1, 1e9);
    lisLast[0] = -1e9;
    vector<int> lisLastIndex(a.size() + 1, -1);
    vector<int> from(a.size(), -1);

    for (int i = 0; i < a.size(); i++) {
        int lisSize = lower_bound(lisLast.begin(), lisLast.end(), a[i]) - lisLast.begin();
        lisLast[lisSize] = a[i];
        lisLastIndex[lisSize] = i;
        from[i] = lisLastIndex[lisSize - 1];
    }

    int lisSize = a.size();
    while (lisLast[lisSize] == 1e9)
        lisSize--;

    vector<int> lis;
    for (int i = lisLastIndex[lisSize]; i != -1; i = from[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());

    return lis;
}

Наибольшая последовательность вкладываемых параллелепипедов

Даны размеры N параллелепипедов. Определить максимальное количество параллелепипедов, которые можно последовательно вложить друг в друга (параллелепипеды можно поворачивать, но рёбра должны быть параллельными осям координат).

Вид подзадачи: Отсортируем параллелепипеды по неубыванию объёма. d[i] — максимальное количество вложенных параллелепипедов, где объемлющим является i-й параллелепипед.

Рекуррентная формула: d[i] = 1 + max(d[j]), где j = 0..(i - 1) и j-й параллелепипед можно вложить в i-й.

База рекурсии: d[0] = 1.

Вид ответа: max(d[i]), где i ∈ 0..(n - 1). Сложность O(N2).

Двумерная динамика (вход — два параметра; подзадача — два меньших параметра)

Биномиальные коэффициенты

Вычислить C(m, n) — количество способов выбрать m предметов из n.

Вид подзадачи: d[i][j] — количество способов выбрать j предметов из i.

Рекуррентная формула: d[i][j] = d[i - 1][j] + d[i - 1][j - 1].

База рекурсии: Если j = 1 или j = i, то d[i][j] = 1.

Вид ответа: d[n][m]. Сложность O(N × M).

Бросание шариков

Есть N-этажное здание и M шариков. Шарики можно бросать с разных этажей; начиная с некоторого этажа X и выше шарики при броске разбиваются. Требуется определить этаж X за наименьшее число бросков. Разбитый шарик нельзя бросать снова (количество шариков уменьшается), целый — можно.

Вид подзадачи: d[i][j] — минимальное количество бросков для определения одного из i этажей, если есть j шариков.

Рекуррентная формула: d[i][j] = 1 + min(max(d[k - 1][j - 1], d[n - k][j])), где k = 1..i.

База рекурсии: Если i = 0, то d[i][j] = 0. Если j = 1, то d[i][j] = i (придётся бросать снизу вверх подряд).

Вид ответа: d[n][m]. Сложность O(N2 × M) (*Можно быстрее).

Другие задачи

Двумерная динамика (вход — параметр, последовательность; подзадача — меньший параметр, префикс)

Рюкзак: можем ли набрать вес M

Рюкзак: набрать вес <= M, максимизировать стоимость

Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна.

Вид подзадачи: d[i][j] — максимальная стоимость подмножества предметов от 0-го до (i - 1)-го, общий вес которых не превосходит j.

Рекуррентная формула: d[i][j] = max(d[i - 1][j], d[i - 1][j - w[i - 1]] + p[i - 1]).

База рекурсии: Если i = 0 или j <= 0, то d[i][j] = 0.

Вид ответа: d[n][m]. Сложность O(N × M).

Рюкзак: набрать вес <= M, максимизировать стоимость, предметы можно брать не более K раз

Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. i-й предмет можно брать k[i] раз.

Вид подзадачи: d[i][j] — максимальная стоимость подмножества предметов от 0-го до (i - 1)-го, общий вес которых не превосходит j.

Рекуррентная формула: d[i][j] = max(d[i - 1][j - k * w[i - 1]] + k * p[i - 1]), где k ∈ 0..k[i].

База рекурсии: Если i = 0 или j <= 0, то d[i][j] = 0.

Вид ответа: d[n][m]. Сложность O(N × M2).

Рюкзак: разделить на две кучи близкого веса

Дано N камней, i-й из которых имеет целочисленный вес 0 < w[i] <= M. Разделить камни на две кучи как можно более близкого веса, вывести разность весов куч.

Вид подзадачи: d[i][j] — 1, если можно набрать кучу веса j из подмножества камней от 0-го до (i - 1)-го, или 0 в противном случае.

Рекуррентная формула: d[i][j] = d[i - 1][j - w[i]].

База рекурсии: d[0][0] = 1.

Вид ответа: min(|j - (∑w - j)|), где d[n][j] = 1. Сложность O(N2 × M).

Число способов восстановления скобок заменой

Дана строка S, состоящая из символов '(', ')' и '?'. Найти количество способов заменить знаки вопроса на скобки так, чтобы получилась правильная скобочная последовательность.

Вид подзадачи: d[i][j] — количество способов восстановить подстроку 0..(i - 1), чтобы в ней было j непарных открывающих скобок.

Рекуррентная формула: Если s[i - 1] = '(', то d[i][j] = d[i - 1][j - 1]. Если s[i - 1] = ')', то d[i][j] = d[i - 1][j + 1]. Если s[i - 1] = '?', то d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1].

База рекурсии: d[0][0] = 1; если j < 0 или j > i, то d[i][j] = 0.

Вид ответа: d[n][0]. Сложность O(N2).

Другие задачи

Двумерная динамика (вход — последовательность; подзадача — подотрезок)

Перемножение цепочки матриц

Даны размеры h[] и w[] для N матриц, причём w[i] = h[i + 1]. Перемножение матрицы i на матрицу (i + 1) требует (h[i] × w[i] × w[i + 1]) операций. Определить минимальное количество операций, требуемое для перемножения всех матриц.

Вид подзадачи: d[i][j] — минимальное количество операций, требуемое для перемножения матриц от i до j.

Рекуррентная формула: d[i][j] = min(d[i][k] + d[k + 1][j] + h[i] * w[k] * w[j]), где k ∈ i..(j - 1).

База рекурсии: d[i][i] = 0.

Вид ответа: d[0][n - 1]. Сложность O(N3).

Число способов получить палиндром удалением символов

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

Вид подзадачи: d[i][j] — количество способов получить палиндром из подстроки S[i..j].

Рекуррентная формула: Если s[i] != s[j], то d[i][j] = d[i + 1][j] + d[i][j - 1] - d[i + 1][j - 1], иначе d[i][j] = d[i + 1][j] + d[i][j - 1] + 1.

База рекурсии: d[i][i] = 1; если i < j, то d[i][j] = 0.

Вид ответа: d[0][n - 1]. Сложность O(N2).

Число действий для восстановления скобок вставкой

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

Вид подзадачи: d[i][j] — минимальное количество символов, которые требуется добавить в подстроку S[i..j], чтобы получилась правильная скобочная последовательность.

Рекуррентная формула: d[i][j] = min(d[i][k] + d[k + 1][j]), где k ∈ i..(j - 1); если S[i] и S[j] — соответствующие открывающая и закрывающая скобки, то d[i][j] = min(d[i][j], d[i + 1][j - 1]).

База рекурсии: d[i][i] = 1; если i < j, то d[i][j] = 0.

Вид ответа: d[0][n - 1]. Сложность O(N3).

Игра со стиранием концов ленты

Есть лента A[], на которой записано N чисел. Два игрока поочерёдно стирают с ленты первое или последнее число и добавляют его к своей сумме. Какую максимальную сумму может получить первый игрок?

Вид подзадачи: d[i][j] — максимальная сумма, которую может набрать начинающий игрок на подотрезке ленты [i..j].

Рекуррентная формула: d[i][j] = max(A[i] + ∑A((i + 1)..j) - d[i + 1][j], A[j] + ∑A(i..(j - 1)) - d[i][j - 1]).

База рекурсии: d[i][i] = A[i].

Вид ответа: d[0][n - 1]. Сложность O(N2).

Двумерная динамика (вход — две последовательности; подзадача — два префикса)

Редакционное расстояние

Дана строка A длины N и строка B длины M. Вставка символа стоит Ci, удаление — Cd, замена — Cr. Найти минимальную стоимость получения строки B из строки A.

Вид подзадачи: d[i][j] — минимальная стоимость получения префикса B[0..(j - 1)] из префикса A[0..(i - 1)].

Рекуррентная формула: d[i][j] = min(d[i][j - 1] + Ci, d[i - 1][j] + Cd, d[i - 1][j - 1] + X), где X = Cr, если A[i - 1] ≠ B[j - 1], иначе X = 0.

База рекурсии: d[0][0] = 0.

Вид ответа: d[n][m]. Сложность O(N × M).

Наибольшая общая подпоследовательность (LCS)

Дана строка A длины N и строка B длины M. Найти длину их наибольшей общей подпоследовательности.

Вид подзадачи: d[i][j] — длина наибольшей общей подпоследовательности префиксов A[0..(i - 1)] и B[0..(j - 1)].

Рекуррентная формула: Если A[i - 1] = B[j - 1], то d[i][j] = d[i - 1][j - 1] + 1, иначе d[i][j] = max(d[i - 1][j], d[i][j - 1]).

База рекурсии: d[0][0] = 0.

Вид ответа: d[n][m]. Сложность O(N × M).

Соответствие строки шаблону

Дана строка S и шаблон P, который может включать символы '?' и '*'. Проверить соответствие строки шаблону.

Вид подзадачи: d[i][j] — соответствие префикса строки 0..(i - 1) префиксу шаблона 0..(j - 1).

Рекуррентная формула: Если p[j - 1] = '?' или p[j - 1] = s[i - 1], то d[i][j] = d[i - 1][j - 1]. Если p[j - 1] = '*', то d[i][j] = or(d[k][j - 1]), где k ∈ 0..i. d[0][0] = 1.

База рекурсии: d[i][0] = 0, где i ∈ 1..n; d[0][j] = 0, где j ∈ 1..m; если j < 0 или j > i, то d[i][j] = 0.

Вид ответа: d[n][m]. Сложность O(N2 × M).

Двумерная динамика (вход — две последовательности; подзадача — два префикса; модификация)

Наибольшая общая подстрока

Дана строка A длины N и строка B длины M. Найти длину их наибольшей общей подстроки.

Вид подзадачи: d[i][j] — длина наибольшей общей подстроки префиксов A[0..(i - 1)] и B[0..(j - 1)], заканчивающейся в них на позициях (i - 1) и (j - 1) соответственно.

Рекуррентная формула: Если A[i - 1] = B[j - 1], то d[i][j] = d[i - 1][j - 1] + 1, иначе d[i][j] = 0.

База рекурсии: d[0][0] = 0.

Вид ответа: max(d[i][j]), i ∈ 1..N. j ∈ 1..M. Сложность O(N × M).

Двумерная динамика (вход — таблица; подзадача — двумерный префикс)

Количество путей в таблице

Дана таблица n × m клеток. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти количество различных путей фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.

Вид подзадачи: d[i][j] — количество путей из клетки [0, 0] в клетку [i, j].

Рекуррентная формула: d[i][j] = d[i - 1][j] + d[i][j - 1].

База рекурсии: d[0][0] = 1; если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = 0.

Вид ответа: d[n][m]. Сложность O(N × M).

Максимальный путь в таблице

Дана таблица n × m клеток, в каждой клетке которой записано число. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти максимально возможную сумму чисел на посещённых клетках при перемещении фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.

Вид подзадачи: d[i][j] — максимальная сумма на пути из клетки [0, 0] в клетку [i, j].

Рекуррентная формула: d[i][j] = a[i][j] + max(d[i - 1][j], d[i][j - 1]).

База рекурсии: d[0][0] = a[0][0]; если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = -INF.

Вид ответа: d[n][m]. Сложность O(N × M).

Двумерная динамика (вход — таблица; подзадача — двумерный префикс; модификация)

Максимальный квадрат из единиц

Дана двоичная матрица размера n × m. Определить максимальную площадь её квадратной подматрицы, состоящей только из единиц.

Вид подзадачи: d[i][j] — сторона максимального единичного квадрата с правым нижним углом в клетке [i, j].

Рекуррентная формула: d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1]).

База рекурсии: d[0][0] = a[0][0]; если a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0.

Вид ответа: max(d[i][j])2, где i ∈ 0..(n - 1), j ∈ 0..(m - 1). Сложность O(N × M).

Динамика на подмножествах

Динамика на деревьях

Другие задачи

Ссылки