Подготовить серию статей об оптимизации динамического программирования

[vaid-via]

Предлагается сделать серию из двух статей об оптимизации динамического программирования (DP).

Часть 1. Базовые оптимизации

• Использование битмасок и перебора подмасок; шаблон полного перебора состояний.
• Сжатие состояний (rolling array) для уменьшения потребления памяти.
• Монотонные очереди и двухконечные деки для оптимизации DP на подмасон.
• Двоичный поиск по ответу, префиксные суммы и сворачивание слоёв.
• Примеры задач: бинарный поиск ответа, оптимизация LCS, битмаски в рюкзаках.

Часть 2. Продвинутые техники

• Divide-and-Conquer DP: применимо к рекуррентным формулам вида dp(i,j) = min_{k≤j} [dp(i‑1,k‑1)+C(k,j)]. При условии, что оптимальный индекс k не убывает, сложность снижается с O(m·n^2) до O(m·n·log n)【763225827960199†L259-L323】.
• Knuth’s Optimization: для DP на диапазонах ( например, «Оптимальное склеивание» ). Использует квадрангельное неравенство и обеспечивает переход от O(n^3) к O(n^2)【9055875667387†L262-L272】, при условии монотонности оптимальных позиций【9055875667387†L274-L333】.
• Convex Hull Trick (CHT): для линейных переходов, когда функция стоимости является линейной. Позволяет уменьшить сложность до O(n) или O(n log n).
• Mo’s Algorithm / Divide-and-Conquer on Queries: оптимизация DP с массивами запросов, когда DP можно вычислить в offline-режиме.
• Другие методы: Sparse Table для RMQ, разрежённые DP, dp на деревьях с heavy‑light decomposition.

Что включить

Для каждой техники нужен краткий вывод условий применимости, математическое обоснование и пример задачи (Codeforces, AtCoder DP Contest). В конце указать литературу, например cp-algorithms и лекции о DP.