Динамическое программирование: Лесенки, наибольшая возрастающая последовательность за O(nlog(n)), по подотрезкам, по подмножествам, ДП по поддереву. ДП по профилю, ДП по изломанному профилю

• Динамика

Динамическое программирование по профилю - способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое.

Профиль - один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.

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

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

Пусть у нас есть правило по которому надо заполнить и для него нам надо $k$ предыдущих линий. Тогда можно перебрать все замощения длиной $k\times n$. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобиться $O(a^{nm})$ времени, а если перебирать только состояния и переходить по ним нам потребуется $O(a^{kn}*m)$ времени (где $а$ - количество способов замещения 1 клетки).