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

Одномерная динамика

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

Найти 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 клеток, в каждой клетке которой записано число. Фишка находится в клетке 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(N²).

Двумерная динамика

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

Дана таблица 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])², где i ∈ 0..(n - 1), j ∈ 0..(m - 1). Сложность O(N × M).