🧠 Напреднало Динамично Програмиране (Advanced DP)
След като овладеете класическото DP (Раница, LIS, LCS), следващото ниво включва техники за оптимизация на състоянията и преходите. Напредналите DP техники ви позволяват да решавате задачи с по-сложни структури от данни (дървета, графи, битови маски) и да оптимизирате сложността от \(O(N^2)\) или \(O(N^3)\) до \(O(N \log N)\) или дори \(O(N)\).
1. ДП върху Дърво (Tree DP)
Задачите върху дървета често се решават с DFS, като за всеки връх \(u\) изчисляваме \(dp[u]\) на базата на децата му. Идеята е да разглеждаме дървото рекурсивно - първо обработваме поддърветата, после комбинираме резултатите.
1.1. Класическо Tree DP
Пример: Максимално независимо множество (Maximum Independent Set) в дърво.
Определяме състояния: - \(dp[u][0]\): максимален брой избрани върхове в поддървото на \(u\), когато \(u\) не е избран - \(dp[u][1]\): максимален брой избрани върхове в поддървото на \(u\), когато \(u\) е избран
Преходи: - Ако \(u\) не е избран: \(dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])\) - Ако \(u\) е избран: \(dp[u][1] = 1 + \sum_{v \in children(u)} dp[v][0]\)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int dp[MAXN][2];
void dfs(int u, int parent) {
dp[u][0] = 0; // u не е избран
dp[u][1] = 1; // u е избран
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
// Ако u не е избран, детето може да е или да не е
dp[u][0] += max(dp[v][0], dp[v][1]);
// Ако u е избран, детето не може да е избрано
dp[u][1] += dp[v][0];
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]) << endl;
return 0;
}
1.2. Още примери за Tree DP
Диаметър на дърво: За всеки връх пазим най-дългия път, който минава през него.
int maxPath[MAXN]; // най-дългият път минаващ през u
int maxDown[MAXN]; // най-дългият път надолу от u
void dfs(int u, int p) {
maxDown[u] = 0;
int max1 = 0, max2 = 0; // двата най-дълги пътя надолу
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
int curr = maxDown[v] + 1;
if (curr > max1) {
max2 = max1;
max1 = curr;
} else if (curr > max2) {
max2 = curr;
}
}
maxDown[u] = max1;
maxPath[u] = max1 + max2; // диаметърът минаващ през u
}
1.3. Rerooting Technique (ДП с всички корени)
Ако трябва да намерим отговора за всеки връх, ако той беше корен.
Подход (два DFS-а): 1. Bottom-up DFS: Пресмятаме DP за произволен корен (напр. 1), обработвайки поддърветата. 2. Top-down DFS: Прехвърляме резултата от родителя към детето, "премествайки" корена.
Пример: За всеки връх намери сумата от разстоянията до всички други върхове.
const int MAXN = 200005;
vector<int> adj[MAXN];
long long subtree[MAXN]; // брой върхове в поддървото
long long down[MAXN]; // сума на разстоянията надолу
long long ans[MAXN]; // отговор за всеки връх
int n;
// Bottom-up: изчисляваме за корен 1
void dfs1(int u, int p) {
subtree[u] = 1;
down[u] = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u);
subtree[u] += subtree[v];
down[u] += down[v] + subtree[v];
}
}
// Top-down: пренасяме резултата към всички възможни корени
void dfs2(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
// Преместваме корена от u към v
// Премахваме принос от поддървото на v
// Добавяме принос от останалото дърво
ans[v] = ans[u] - subtree[v] + (n - subtree[v]);
dfs2(v, u);
}
}
2. ДП върху Профил (Broken Profile DP)
Използва се за покриване на мрежи \(N \times M\) с фигури (домино, плочки), където \(N\) е малко (обикновено \(N \le 13\)).
Състоянието е битова маска, представляваща границата ("профила") между обработената и необработената част на мрежата. Обработваме мрежата колона по колона (или ред по ред).
Пример: Покриване на \(N \times M\) шахматна дъска с \(1 \times 2\) домина.
Битовата маска показва кои клетки от текущата колона "излизат" в следващата (вертикални домина).
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long dp[1005][1 << 13]; // dp[колона][маска]
bool valid[1 << 13][1 << 13]; // валидни преходи
// Проверка дали можем да преминем от маска cur към next
void precompute(int pos, int cur, int next, int curMask, int nextMask) {
if (pos == n) {
valid[curMask][nextMask] = true;
return;
}
if (cur & (1 << pos)) {
// Тази клетка е заета от предишна колона
precompute(pos + 1, cur, next, curMask, nextMask);
} else {
// Поставяме вертикално домино
precompute(pos + 1, cur | (1 << pos), next | (1 << pos),
curMask, nextMask | (1 << pos));
// Поставяме хоризонтално домино (ако има място)
if (pos + 1 < n && !(cur & (1 << (pos + 1)))) {
precompute(pos + 2, cur | (1 << pos) | (1 << (pos + 1)),
next, curMask, nextMask);
}
}
}
int main() {
cin >> n >> m;
// Предварително изчисляваме валидните преходи
for (int mask = 0; mask < (1 << n); mask++) {
precompute(0, mask, 0, mask, 0);
}
dp[0][0] = 1; // Начална конфигурация
for (int col = 0; col < m; col++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[col][mask] == 0) continue;
for (int nextMask = 0; nextMask < (1 << n); nextMask++) {
if (valid[mask][nextMask]) {
dp[col + 1][nextMask] += dp[col][mask];
}
}
}
}
cout << dp[m][0] << endl; // Всички клетки трябва да са покрити
return 0;
}
Сложност: \(O(N \cdot M \cdot 2^N \cdot 2^N)\) за предварителното изчисление, \(O(M \cdot 2^{2N})\) за DP.
3. ДП с Битови Маски (Bitmask DP)
Използва се когато имаме малко множество от елементи (\(N \le 20\)) и трябва да пазим информация за поднеждествата.
Пример: Travelling Salesman Problem (TSP)
Състояние: \(dp[mask][i]\) = минимална цена да посетим върховете в \(mask\) и да завършим на връх \(i\).
const int MAXN = 20;
const int INF = 1e9;
int dist[MAXN][MAXN];
int dp[1 << MAXN][MAXN];
int n;
int tsp() {
// Инициализация
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
dp[mask][i] = INF;
}
}
// Започваме от връх 0
dp[1][0] = 0;
// За всяка маска (множество от посетени върхове)
for (int mask = 1; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue; // i трябва да е в маската
if (dp[mask][i] == INF) continue;
// Опитваме да добавим връх j
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) continue; // j вече е посетен
int newMask = mask | (1 << j);
dp[newMask][j] = min(dp[newMask][j],
dp[mask][i] + dist[i][j]);
}
}
}
// Намираме минималната цена за посещение на всички върхове
int fullMask = (1 << n) - 1;
int result = INF;
for (int i = 0; i < n; i++) {
result = min(result, dp[fullMask][i] + dist[i][0]); // връщаме се в началото
}
return result;
}
Оптимизация: Subset Sum с битови операции
Ако имаме множество числа и искаме да намерим всички възможни суми, можем да използваме bitset:
#include <bitset>
bitset<100005> dp;
void subsetSum(vector<int>& nums) {
dp[0] = 1; // сумата 0 е възможна
for (int x : nums) {
dp |= (dp << x); // добавяме x към всички възможни суми
}
}
4. Digit DP (ДП с Цифри)
Използва се за броене на числа в интервал \([L, R]\), които удовлетворяват определено свойство.
Подход: Броим числа от \([0, R]\) минус числа от \([0, L-1]\).
Състояние: \(dp[pos][tight][started][...]\) където: - \(pos\) = текуща позиция в числото - \(tight\) = дали сме още ограничени от горната граница - \(started\) = дали сме започнали да поставяме ненулеви цифри - допълнителни параметри според задачата
Пример: Броене на числа в \([L, R]\) със сума на цифрите, делима на \(K\).
#include <bits/stdc++.h>
using namespace std;
string num;
int K;
int dp[20][2][2][200]; // [pos][tight][started][sum % K]
// Рекурсивна функция за digit DP
int solve(int pos, int tight, int started, int sum) {
// Базов случай: обработени всички цифри
if (pos == num.size()) {
return started && (sum % K == 0);
}
// Мемоизация
if (dp[pos][tight][started][sum] != -1) {
return dp[pos][tight][started][sum];
}
int limit = tight ? (num[pos] - '0') : 9;
int result = 0;
for (int digit = 0; digit <= limit; digit++) {
int newTight = tight && (digit == limit);
int newStarted = started || (digit > 0);
int newSum = sum + digit;
result += solve(pos + 1, newTight, newStarted, newSum);
}
return dp[pos][tight][started][sum] = result;
}
int countNumbers(long long x) {
if (x < 0) return 0;
num = to_string(x);
memset(dp, -1, sizeof(dp));
return solve(0, 1, 0, 0);
}
int main() {
long long L, R;
cin >> L >> R >> K;
int answer = countNumbers(R) - countNumbers(L - 1);
cout << answer << endl;
return 0;
}
Други приложения на Digit DP: - Числа без последователни еднакви цифри - Числа с точно K различни цифри - Числа, чиито цифри формират растяща/намаляваща последователност - Числа, делими на сумата на цифрите си
5. Оптимизации на преходите
Много DP задачи имат формула от вида: \(dp[i] = \min_{j < i} \{ dp[j] + cost(j, i) \}\)
Директното пресмятане е \(O(N^2)\). Целта е да го сведем до \(O(N \log N)\) или \(O(N)\).
5.1. Convex Hull Trick (CHT)
Приложимо когато \(cost(j, i)\) може да се представи като линейна функция: \(cost(j, i) = b_j \cdot a_i + c_j\)
Тогава: \(dp[i] = \min_{j < i} \{ dp[j] + b_j \cdot a_i + c_j \} = \min_{j < i} \{ (dp[j] + c_j) + b_j \cdot a_i \}\)
Всяко \(j\) дефинира права с наклон \(m_j = b_j\) и свободен член \(c_j = dp[j] + c_j\).
Идея: Поддържаме долната изпъкнала обвивка на правите. За всяко \(a_i\) намираме правата с минимална стойност.
Имплементация с Deque (когато наклоните са монотонни):
struct Line {
long long m, c; // y = m*x + c
long long eval(long long x) { return m * x + c; }
};
deque<Line> hull;
// Проверка дали средната права е излишна
bool bad(Line l1, Line l2, Line l3) {
// l2 е лоша ако l1 и l3 се пресичат преди l1 и l2
return (__int128)(l3.c - l1.c) * (l1.m - l2.m) <=
(__int128)(l2.c - l1.c) * (l1.m - l3.m);
}
void addLine(Line newLine) {
// Премахваме лоши прави от края
while (hull.size() >= 2 &&
bad(hull[hull.size()-2], hull[hull.size()-1], newLine)) {
hull.pop_back();
}
hull.push_back(newLine);
}
long long query(long long x) {
// Ако x-овете са монотонни, можем да премахваме от началото
while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
hull.pop_front();
}
return hull[0].eval(x);
}
Пример задача: Имаме масиви \(a[]\) и \(b[]\). Трябва да изчислим: \(dp[i] = \min_{j < i} \{ dp[j] + b[j] \cdot a[i] \}\)
const int MAXN = 100005;
long long a[MAXN], b[MAXN], dp[MAXN];
int n;
void solve() {
dp[0] = 0;
addLine({b[0], dp[0]});
for (int i = 1; i < n; i++) {
dp[i] = query(a[i]);
addLine({b[i], dp[i]});
}
}
Сложност: \(O(N)\) ако наклоните и \(x\)-овете са монотонни.
5.2. Divide and Conquer Optimization
Приложимо когато оптималната точка на прехода е монотонна: \(opt[i] \le opt[i+1]\).
Условие (Quadrangle Inequality): \(cost(a, c) + cost(b, d) \le cost(a, d) + cost(b, c)\) за \(a \le b \le c \le d\).
Пример: \(dp[i][k]\) = минимална цена да разделим първите \(i\) елемента на \(k\) групи.
const int MAXN = 5005;
const long long INF = 1e18;
long long dp[MAXN][MAXN];
long long cost[MAXN][MAXN]; // предварително изчислена цена
void compute(int k, int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
long long best = INF;
int bestPos = -1;
// Търсим оптималната позиция в ограничен интервал
for (int j = optL; j <= min(mid, optR); j++) {
long long curr = dp[j][k-1] + cost[j+1][mid];
if (curr < best) {
best = curr;
bestPos = j;
}
}
dp[mid][k] = best;
// Рекурсивно за лявата и дясната половина
compute(k, l, mid - 1, optL, bestPos);
compute(k, mid + 1, r, bestPos, optR);
}
void solve() {
// Инициализация
for (int i = 0; i < n; i++) {
dp[i][0] = INF;
dp[i][1] = cost[0][i];
}
// За всяко k
for (int k = 2; k <= maxK; k++) {
compute(k, 0, n - 1, 0, n - 1);
}
}
Сложност: \(O(K \cdot N \log N)\) вместо \(O(K \cdot N^2)\).
5.3. Knuth Optimization
Приложимо за интервални DP задачи с квадратно неравенство.
Условия: 1. \(opt[i][j-1] \le opt[i][j] \le opt[i+1][j]\) (монотонност на оптимума) 2. \(cost(i, j)\) удовлетворява квадратното неравенство
Пример: Оптимално двоично дърво за търсене (Optimal BST).
const int MAXN = 1005;
long long dp[MAXN][MAXN]; // dp[i][j] = минимална цена за интервал [i, j]
int opt[MAXN][MAXN]; // opt[i][j] = оптимална позиция на корена
long long cost[MAXN][MAXN]; // цена за интервал
void solve() {
// Базов случай
for (int i = 0; i < n; i++) {
dp[i][i] = cost[i][i];
opt[i][i] = i;
}
// По дължина на интервала
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = INF;
// Ограничаваме търсенето с Knuth Optimization
for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
long long curr = dp[i][k-1] + dp[k+1][j] + cost[i][j];
if (curr < dp[i][j]) {
dp[i][j] = curr;
opt[i][j] = k;
}
}
}
}
}
Сложност: \(O(N^2)\) вместо \(O(N^3)\).
6. SOS DP (Sum Over Subsets)
За пресмятане на \(F[mask] = \sum_{sub \subseteq mask} A[sub]\) за всички маски.
Наивен подход: За всяка маска итерираме през всички нейни подмножества.
for (int mask = 0; mask < (1 << n); mask++) {
for (int sub = mask; ; sub = (sub - 1) & mask) {
F[mask] += A[sub];
if (sub == 0) break;
}
}
SOS DP подход: Обработваме битовете един по един.
Идея: \(dp[mask][i]\) = сума на всички подмаски на \(mask\), които се различават само в първите \(i\) бита.
// Инициализация
for (int mask = 0; mask < (1 << n); mask++) {
dp[mask][0] = A[mask];
}
// Итериране по битове
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (mask & (1 << i)) {
// Ако i-тият бит е 1, добавяме подмаските с 0 на тази позиция
dp[mask][i+1] = dp[mask][i] + dp[mask ^ (1 << i)][i];
} else {
// Ако i-тият бит е 0, не добавяме нищо ново
dp[mask][i+1] = dp[mask][i];
}
}
}
// Оптимизирана версия без второ измерение
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (mask & (1 << i)) {
dp[mask] += dp[mask ^ (1 << i)];
}
}
}
Сложност: \(O(N \cdot 2^N)\).
Приложения: - Броене на подмножества с определени свойства - Convolution на два масива върху битови маски - Задачи с обединения и пресичания на множества
Пример задача: Имаме \(N\) цели числа. За всяко число искаме да знаем колко числа от множеството са негови подмаски (имат само битове, които са включени в текущото число).
int count[1 << 20];
int freq[1 << 20];
void countSubsets(vector<int>& nums) {
// freq[mask] = колко пъти се среща маската
for (int x : nums) {
freq[x]++;
}
// SOS DP
for (int i = 0; i < 20; i++) {
for (int mask = 0; mask < (1 << 20); mask++) {
if (mask & (1 << i)) {
freq[mask] += freq[mask ^ (1 << i)];
}
}
}
// freq[mask] сега съдържа броя на подмаските
}
7. Практически съвети и често срещани грешки
7.1. Оптимизация на паметта
Когато DP масивът е многомерен, често можем да намалим размерността: - Ако \(dp[i]\) зависи само от \(dp[i-1]\), използвайте два масива или rolling array - За интервално DP, обработвайте по дължина на интервала
// Вместо dp[n][k], използваме само два реда
long long curr[MAXK], prev[MAXK];
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
curr[j] = prev[j] + transition[i][j];
}
swap(curr, prev);
}
7.2. Избор на структури от данни
За оптимизация на DP преходите: - Segment Tree / Fenwick Tree: За range queries (min, max, sum) - Monotonic Deque: За sliding window минимум/максимум - Set/Map: За динамично поддържане на кандидати - Li Chao Tree: За Convex Hull Trick с произволни наклони
7.3. Често срещани грешки
- Неправилна инициализация: Уверете се, че началните състояния са правилни
- Overflow: Използвайте
long longкъдето е необходимо - Неправилен ред на итерация: При някои оптимизации редът е критичен
- Забравяне на edge cases: Празни множества, единични елементи, etc.
// Пример: Правилна инициализация за минимизация
const long long INF = 1e18;
for (int i = 0; i < n; i++) {
dp[i] = INF; // Не 1e9, защото може да има overflow!
}
dp[0] = 0; // Базов случай
8. Задачи за практика
8.1. Tree DP
- CSES Tree Matching: Максимално matching в дърво
- CSES Tree Distances I: Максимално разстояние от всеки връх
- CSES Tree Distances II: Сума на разстоянията (Rerooting)
- Codeforces 1092F: Tree with Maximum Cost
8.2. Bitmask DP
- CSES Hamiltonian Flights: Броене на Hamiltonian paths
- CSES Elevator Rides: Оптимално разпределение с ограничение
- Codeforces 453B: Little Pony and Harmony Chest
- AtCoder DP Contest - O: Matching
8.3. Digit DP
- SPOJ GONE: Числа с определена сума на цифрите
- Codeforces 628D: Magic Numbers
- LightOJ 1068: Investigating Palindromes (с digit DP)
8.4. Оптимизации
- Codeforces 319C: Kalila and Dimna (Convex Hull Trick)
- APIO 2010: Commando (CHT)
- IOI 2014: Holiday (Divide and Conquer)
- CEOI 2004: Two Sawmills (Knuth Optimization)
8.5. SOS DP
- Codeforces 165E: Compatible Numbers
- Codeforces 449D: Jzzhu and Numbers
- CSES Sum of Four Values: (с битови маски)
9. Допълнителни техники
9.1. DP с Matrix Exponentiation
За DP с линейни преходи, когато \(N\) е много голямо, можем да използваме матрично умножение.
Пример: Fibonacci с матрици за \(O(\log N)\):
typedef vector<vector<long long>> Matrix;
Matrix multiply(Matrix& A, Matrix& B) {
int n = A.size();
Matrix C(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
Matrix matPow(Matrix A, long long p) {
int n = A.size();
Matrix result(n, vector<long long>(n, 0));
// Единична матрица
for (int i = 0; i < n; i++) result[i][i] = 1;
while (p > 0) {
if (p & 1) result = multiply(result, A);
A = multiply(A, A);
p >>= 1;
}
return result;
}
9.2. Monotone Queue Optimization
За оптимизация на DP от вида \(dp[i] = \min_{i-k \le j < i} dp[j] + cost[j]\).
deque<int> dq; // съхранява индекси
for (int i = 0; i < n; i++) {
// Премахваме елементи извън прозореца
while (!dq.empty() && dq.front() < i - k) {
dq.pop_front();
}
// Намираме минимума в прозореца
if (!dq.empty()) {
dp[i] = dp[dq.front()] + cost[i];
}
// Добавяме текущия елемент
while (!dq.empty() && dp[dq.back()] >= dp[i]) {
dq.pop_back();
}
dq.push_back(i);
}
🏁 Заключение
Advanced DP е изкуството да превърнеш "невъзможното" \(O(N^2)\) или \(O(N^3)\) решение в \(O(N \log N)\) или \(O(N)\) чрез математически наблюдения и структури от данни.
Ключови стъпки при решаване на Advanced DP задачи:
- Разпознаване на типа: Tree DP, Bitmask DP, Digit DP, Profile DP?
- Формулиране на състоянията: Какво трябва да помним за да изчислим отговора?
- Намиране на преходите: Как комбинираме по-малките подзадачи?
- Оптимизация: Има ли монотонност? Можем ли да използваме CHT, D&C, Knuth?
- Имплементация: Внимавайте за overflow, правилна инициализация, edge cases
Практикувайте редовно и анализирайте решенията на задачи от състезания. С времето ще развиете интуиция кога коя техника е приложима.
Ресурси за допълнително обучение: - CSES Problem Set (Advanced DP секция) - Codeforces EDU section - AtCoder DP Contest - CP-Algorithms website - IOI/CEOI/APIO архиви със задачи
Успех с напредналото динамично програмиране! 🚀