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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
== Простая одномерная динамика ==
== Одномерная динамика (вход — параметр; подзадача — меньший параметр) ==


=== Числа Фибоначчи ===
=== Числа Фибоначчи ===
Строка 10: Строка 10:


Вид ответа: d[n]. Сложность O(N). (*Данная задача может быть решена за O(logN).)
Вид ответа: d[n]. Сложность O(N). (*Данная задача может быть решена за O(logN).)
=== Задача о рюкзаке с повторениями ===
Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. Каждый предмет можно брать неограниченное число раз.
Вид подзадачи: d[j] — максимальная стоимость подмножества предметов, общий вес которых не превосходит j.
Рекуррентная формула: Если j <= 0, то d[j] = 0, иначе d[j] = max(d[j - w[i]] + p[i]), где i &isin; 0..(n - 1).
Вид ответа: d[m]. Сложность O(N &times; M).
== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс) ==


=== Количество путей в полосе ===
=== Количество путей в полосе ===
Строка 31: Строка 43:
Вид ответа: d[n]. Сложность O(N).
Вид ответа: d[n]. Сложность O(N).


=== Задача о рюкзаке с повторениями ===
== Одномерная динамика (вход &mdash; последовательность; подзадача &mdash; префикс + привязка) ==
 
Дано N предметов, i-й из которых имеет целочисленные вес w[i] > 0 и стоимость p[i] > 0. Выбрать часть предметов так, чтобы их общий вес не превышал M, а общая стоимость была максимальна. Каждый предмет можно брать неограниченное число раз.
 
Вид подзадачи: d[j] &mdash; максимальная стоимость подмножества предметов, общий вес которых не превосходит j.
 
Рекуррентная формула: Если j <= 0, то d[j] = 0, иначе d[j] = max(d[j - w[i]] + p[i]), где i &isin; 0..(n - 1).
 
Вид ответа: d[m]. Сложность O(N &times; M).
 
== Менее тривиальная одномерная динамика ==


=== Подотрезок с максимальной суммой ===
=== Подотрезок с максимальной суммой ===
Строка 75: Строка 77:
Вид ответа: 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>).


== Простая двумерная динамика ==
== Двумерная динамика (вход &mdash; параметр, последовательность; подзадача &mdash; меньший параметр, префикс) ==
 
=== Количество путей в таблице ===
 
Дана таблица n &times; m клеток. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти количество различных путей фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.
 
Вид подзадачи: d[i][j] &mdash; количество путей из клетки [0, 0] в клетку [i, j].
 
Рекуррентная формула: Если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = 0, иначе d[i][j] = d[i - 1][j] + d[i][j - 1]; d[0][0] = 1.
 
Вид ответа: d[n][m]. Сложность O(N &times; M).
 
=== Максимальный путь в таблице ===
 
Дана таблица n &times; m клеток, в каждой клетке которой записано число. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти максимально возможную сумму чисел на посещённых клетках при перемещении фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.
 
Вид подзадачи: d[i][j] &mdash; максимальная сумма на пути из клетки [0, 0] в клетку [i, j].
 
Рекуррентная формула: Если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = -INF, иначе d[i][j] = a[i][j] + max(d[i - 1][j], d[i][j - 1]); d[0][0] = a[0][0].
 
Вид ответа: d[n][m]. Сложность O(N &times; M).
 
* [http://acmp.ru/index.asp?main=task&id_task=120 ACMP #120 &mdash; Минимальный путь в таблице]


=== Задача о рюкзаке без повторений ===
=== Задача о рюкзаке без повторений ===
Строка 119: Строка 99:
Вид ответа: d[n][m]. Сложность O(N &times; M<sup>2</sup>).
Вид ответа: d[n][m]. Сложность O(N &times; M<sup>2</sup>).


== Менее тривиальная двумерная динамика ==
=== Восстановление скобок ===
 
Дана строка S, состоящая из символов '(', ')' и '?'. Найти количество способов заменить знаки вопроса на скобки так, чтобы получилась правильная скобочная последовательность.
 
Вид подзадачи: d[i][j] &mdash; количество способов восстановить подстроку 0..(i - 1), чтобы в ней было j непарных открывающих скобок.


=== Максимальный квадрат из единиц ===
Рекуррентная формула: Если j < 0 или j > i, то d[i][j] = 0. Если 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.


Дана двоичная матрица размера n &times; m. Определить максимальную площадь её квадратной подматрицы, состоящей только из единиц.
Вид ответа: d[n][0]. Сложность O(N<sup>2</sup>).


Вид подзадачи: d[i][j] &mdash; сторона максимального единичного квадрата с правым нижним углом в клетке [i, j].
* [http://acmp.ru/index.asp?main=task&id_task=123 ACMP #123 &mdash; Восстановление скобок]


Рекуррентная формула: Если клетка a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0, иначе d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i][j - 1]); d[0][0] = a[0][0].
== Двумерная динамика (вход &mdash; последовательность; подзадача &mdash; подотрезок) ==


Вид ответа: max(d[i][j])<sup>2</sup>, где i &isin; 0..(n - 1), j &isin; 0..(m - 1). Сложность O(N &times; M).
=== Перемножение цепочки матриц ===


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


Дана строка S, состоящая из символов '(', ')' и '?'. Найти количество способов заменить знаки вопроса на скобки так, чтобы получилась правильная скобочная последовательность.
Вид подзадачи: d[i][j] &mdash; минимальное количество операций, требуемое для перемножения матриц от i до j.


Вид подзадачи: d[i][j] &mdash; количество способов восстановить подстроку 0..(i - 1), чтобы в ней было j непарных открывающих скобок.
Рекуррентная формула: d[i][i] = 0, d[i][j] = min(d[i][k] + d[k + 1][j] + h[i] * w[k] * w[j]), где k &isin; i..(j - 1).


Рекуррентная формула: Если j < 0 или j > i, то d[i][j] = 0. Если 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.
Вид ответа: d[0][n - 1]. Сложность O(N<sup>3</sup>).


Вид ответа: d[n][0]. Сложность O(N<sup>2</sup>).
* [http://acmp.ru/index.asp?main=task&id_task=553 ACMP #553 &mdash; Объединение блоков]


* [http://acmp.ru/index.asp?main=task&id_task=123 ACMP #123 &mdash; Восстановление скобок]
== Двумерная динамика (вход &mdash; две последовательности; подзадача &mdash; два префикса) ==


=== Соответствие строки шаблону ===
=== Соответствие строки шаблону ===
Строка 153: Строка 137:
Вид ответа: 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 #123 &mdash; Шаблон]
* [http://acmp.ru/index.asp?main=task&id_task=104 ACMP #104 &mdash; Шаблон]
 
== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс) ==
 
=== Количество путей в таблице ===
 
Дана таблица n &times; m клеток. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти количество различных путей фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.
 
Вид подзадачи: d[i][j] &mdash; количество путей из клетки [0, 0] в клетку [i, j].
 
Рекуррентная формула: Если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = 0, иначе d[i][j] = d[i - 1][j] + d[i][j - 1]; d[0][0] = 1.
 
Вид ответа: d[n][m]. Сложность O(N &times; M).
 
=== Максимальный путь в таблице ===
 
Дана таблица n &times; m клеток, в каждой клетке которой записано число. Фишка находится в клетке [0, 0] и может перемещаться вправо или вниз. Найти максимально возможную сумму чисел на посещённых клетках при перемещении фишки от клетки [0, 0] до клетки [n - 1, m - 1]. Некоторые клетки могут быть непроходимыми.
 
Вид подзадачи: d[i][j] &mdash; максимальная сумма на пути из клетки [0, 0] в клетку [i, j].
 
Рекуррентная формула: Если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = -INF, иначе d[i][j] = a[i][j] + max(d[i - 1][j], d[i][j - 1]); d[0][0] = a[0][0].
 
Вид ответа: d[n][m]. Сложность O(N &times; M).
 
* [http://acmp.ru/index.asp?main=task&id_task=120 ACMP #120 &mdash; Минимальный путь в таблице]
 
== Двумерная динамика (вход &mdash; таблица; подзадача &mdash; двумерный префикс + привязка) ==
 
=== Максимальный квадрат из единиц ===
 
Дана двоичная матрица размера n &times; m. Определить максимальную площадь её квадратной подматрицы, состоящей только из единиц.
 
Вид подзадачи: d[i][j] &mdash; сторона максимального единичного квадрата с правым нижним углом в клетке [i, j].
 
Рекуррентная формула: Если клетка a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0, иначе d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i][j - 1]); d[0][0] = a[0][0].
 
Вид ответа: max(d[i][j])<sup>2</sup>, где i &isin; 0..(n - 1), j &isin; 0..(m - 1). Сложность O(N &times; M).

Версия от 05:29, 17 августа 2014

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

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

Найти 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).)

Задача о рюкзаке с повторениями

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

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

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

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

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

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

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

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

Рекуррентная формула: Если i-ая клетка непроходимая или i < 0, то d[i] = 0, иначе d[i] = d[i - 1] + d[i - 2] + d[i - 3]); d[0] = 1.

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

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

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

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

Рекуррентная формула: Если i-ая клетка непроходимая или i < 0, то d[i] = -INF, иначе d[i] = a[i] + max(d[i - 1], d[i - 2], d[i - 3]); d[0] = a[0].

Вид ответа: 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).

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

Даны размеры 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).

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

Задача о рюкзаке без повторений

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

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

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

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

Задача о рюкзаке с ограниченными повторениями

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

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

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

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

Восстановление скобок

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

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

Рекуррентная формула: Если j < 0 или j > i, то d[i][j] = 0. Если 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.

Вид ответа: 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][i] = 0, d[i][j] = min(d[i][k] + d[k + 1][j] + h[i] * w[k] * w[j]), где k ∈ i..(j - 1).

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

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

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

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

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

Рекуррентная формула: Если j < 0 или j > i, то d[i][j] = 0. Если 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.

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

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

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

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

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

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

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

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

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

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

Рекуррентная формула: Если клетка [i, j] непроходимая (либо i < 0 или j < 0), то d[i][j] = -INF, иначе d[i][j] = a[i][j] + max(d[i - 1][j], d[i][j - 1]); d[0][0] = a[0][0].

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

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

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

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

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

Рекуррентная формула: Если клетка a[i][j] = 0 (либо i < 0 или j < 0), то d[i][j] = 0, иначе d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i][j - 1]); d[0][0] = a[0][0].

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