Skip to content

🔄 Динамично програмиране: Разширени техники

🔢 ДП по цифри (Digit DP)

Използва се за задачи от типа "Колко числа в интервала \([A, B]\) удовлетворяват условие \(X\)?". Решаваме задачата за \([0, B]\) и вадим резултата за \([0, A-1]\).

Състояние: dp(index, count, isLess, isStarted) - index: Коя цифра разглеждаме (отляво надясно). - count: Параметърът, който следим (напр. сума на цифрите, брой срещания на цифрата 7 и т.н.). - isLess: Булев флаг. true ако числото, което строим, вече е строго по-малко от префикса на \(N\). Ако е true, можем да слагаме всякакви цифри (0-9). Ако е false, сме ограничени до \(N[index]\). - isStarted: За обработка на водещите нули.

Базов шаблон: 

long long memo[20][200][2];
string S;

long long solve(int idx, int sum, bool isLess) {
    if (idx == S.size()) return sum; // Базов случай
    if (memo[idx][sum][isLess] != -1) return memo[idx][sum][isLess];

    long long ans = 0;
    int limit = isLess ? 9 : (S[idx] - '0');

    for (int digit = 0; digit <= limit; digit++) {
        bool nextIsLess = isLess || (digit < limit);
        ans += solve(idx + 1, sum + digit, nextIsLess);
    }
    return memo[idx][sum][isLess] = ans;
}

Разширен пример: Брой числа със сумата на цифрите, делима на K

#include <iostream>
#include <cstring>
using namespace std;

string num;
int K;
long long dp[20][180][2]; // [позиция][сума % K][isLess]

long long digitDP(int pos, int sum, bool tight) {
    // Базов случай - стигнали сме края на числото
    if (pos == num.size()) {
        return sum == 0 ? 1 : 0;
    }

    // Проверка за мемоизация
    if (dp[pos][sum][tight] != -1) {
        return dp[pos][sum][tight];
    }

    int limit = tight ? (num[pos] - '0') : 9;
    long long result = 0;

    for (int digit = 0; digit <= limit; digit++) {
        int newSum = (sum + digit) % K;
        bool newTight = tight && (digit == limit);
        result += digitDP(pos + 1, newSum, newTight);
    }

    return dp[pos][sum][tight] = result;
}

long long solve(string number) {
    num = number;
    memset(dp, -1, sizeof(dp));
    return digitDP(0, 0, true) - 1; // -1 за да изключим 0
}

int main() {
    K = 3;
    cout << "Числа до 100 със сума на цифрите, делима на 3: " 
         << solve("100") << endl;
    return 0;
}

Трикове при Digit DP:

  1. Обработка на водещи нули: Добавяме флаг isStarted, който става true след първата ненулева цифра.
  2. Интервал \([A, B]\): Пресмятаме solve(B) - solve(A-1).
  3. Оптимизация на паметта: Ако имаме много параметри, можем да използваме map вместо масив за мемоизация.

🌳 ДП в дърво (Tree DP)

Задачи върху дървета често се решават с ДП, където състоянието за възел \(u\) зависи от децата му.

Пример: Максимално независимо множество (Maximum Independent Set) Върни максималния брой върхове, които не са съседи. - dp[u][0]: Максимум за поддървото на \(u\), ако \(u\) не е избран. - \(\sum \max(dp[v][0], dp[v][1])\) за всички деца \(v\). - dp[u][1]: Максимум за поддървото, ако \(u\) е избран. - \(1 + \sum dp[v][0]\) за всички деца \(v\) (децата не могат да бъдат избрани).

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int dp[MAXN][2]; // dp[u][0/1] = не избран/избран
bool visited[MAXN];

void dfs(int u, int parent) {
    visited[u] = true;
    dp[u][0] = 0; // не избираме възел u
    dp[u][1] = 1; // избираме възел u

    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);

        // Ако u не е избран, можем да изберем или да не изберем v
        dp[u][0] += max(dp[v][0], dp[v][1]);

        // Ако u е избран, не можем да изберем v
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int n = 5;
    adj[1] = {2, 3};
    adj[2] = {1, 4, 5};
    adj[3] = {1};
    adj[4] = {2};
    adj[5] = {2};

    dfs(1, -1);
    cout << "Максимално независимо множество: " 
         << max(dp[1][0], dp[1][1]) << endl;
    return 0;
}

Друг пример: Диаметър на дърво с ДП

Диаметърът е най-дългият път между два върха. Можем да го намерим с две DFS обхождания или с ДП:

int diameter = 0;

int dfs(int u, int parent) {
    int max1 = 0, max2 = 0; // Два най-дълги пътя надолу

    for (int v : adj[u]) {
        if (v == parent) continue;
        int h = dfs(v, u);

        if (h > max1) {
            max2 = max1;
            max1 = h;
        } else if (h > max2) {
            max2 = h;
        }
    }

    diameter = max(diameter, max1 + max2);
    return max1 + 1;
}

📏 Алгоритъм на Хиршберг (Hirschberg's Algorithm)

За намиране на самият LCS (Най-дълъг общ подниз), а не само дължината му, стандартното ДП изисква \(O(N \cdot M)\) памет. Хиршберг позволява възстановяване на пътя с \(O(N \cdot M)\) време и само \(O(\min(N, M))\) памет. - Използва "Разделяй и владей", като намира средната точка на оптималния път и решава рекурсивно за двете половини.

Детайлно обяснение:

Стандартният LCS използва таблица \(dp[i][j]\), която отнема \(O(N \cdot M)\) памет. Хиршберг забелязва, че: 1. За да намерим дължината на LCS, ни трябват само два реда наведнъж. 2. Можем да разделим проблема на две части по средата на първия низ. 3. Рекурсивно решаваме двете подзадачи.

// Намиране на последния ред от ДП таблицата
vector<int> computeLCS(string A, string B) {
    int m = A.size(), n = B.size();
    vector<int> prev(n + 1, 0), curr(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i-1] == B[j-1]) {
                curr[j] = prev[j-1] + 1;
            } else {
                curr[j] = max(prev[j], curr[j-1]);
            }
        }
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev;
}

// Рекурсивна функция на Хиршберг
string hirschberg(string A, string B) {
    if (A.empty()) return "";
    if (A.size() == 1) {
        for (char c : B) {
            if (c == A[0]) return string(1, A[0]);
        }
        return "";
    }

    int mid = A.size() / 2;
    string A1 = A.substr(0, mid);
    string A2 = A.substr(mid);

    // Намираме оптималното разделяне на B
    vector<int> L1 = computeLCS(A1, B);

    // Обръщаме низовете за втората половина
    reverse(A2.begin(), A2.end());
    reverse(B.begin(), B.end());
    vector<int> L2 = computeLCS(A2, B);
    reverse(B.begin(), B.end());

    // Намираме най-добрата точка за разделяне
    int k = 0, maxVal = L1[0] + L2[B.size()];
    for (int j = 0; j <= B.size(); j++) {
        if (L1[j] + L2[B.size() - j] > maxVal) {
            maxVal = L1[j] + L2[B.size() - j];
            k = j;
        }
    }

    // Рекурсивно решаваме двете части
    return hirschberg(A1, B.substr(0, k)) + 
           hirschberg(A.substr(mid), B.substr(k));
}

Сложност: \(O(N \cdot M)\) време, \(O(\min(N, M))\) памет.

🎒 Раница (Knapsack) - Вариации

  1. Unbounded Knapsack: Всеки предмет може да се ползва многократно.
  2. \(dp[w] = \max(dp[w], dp[w - weight[i]] + value[i])\) (цикълът е от долу нагоре).
  3. Limited Knapsack: Всеки предмет има \(C_i\) бройки.
  4. Оптимизация: Разлагаме \(C_i\) на степени на двойката \((1, 2, 4, \dots)\) и свеждаме задачата до 0/1 Knapsack (\(O(N \cdot W \cdot \log C)\)).

Детайлна имплементация на Unbounded Knapsack:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int unboundedKnapsack(int W, vector<int>& weight, vector<int>& value) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);

    // За всяко тегло от 1 до W
    for (int w = 1; w <= W; w++) {
        // Пробваме всеки предмет
        for (int i = 0; i < n; i++) {
            if (weight[i] <= w) {
                dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
            }
        }
    }

    return dp[W];
}

int main() {
    int W = 8;
    vector<int> weight = {1, 3, 4, 5};
    vector<int> value = {10, 40, 50, 70};

    cout << "Максимална стойност: " 
         << unboundedKnapsack(W, weight, value) << endl;
    return 0;
}

Limited Knapsack с Binary Decomposition:

int limitedKnapsack(int W, vector<int>& weight, 
                    vector<int>& value, vector<int>& count) {
    int n = weight.size();
    vector<pair<int,int>> items; // {тегло, стойност}

    // Разлагаме всеки предмет на степени на 2
    for (int i = 0; i < n; i++) {
        int c = count[i];
        int k = 1;
        while (k <= c) {
            items.push_back({weight[i] * k, value[i] * k});
            c -= k;
            k *= 2;
        }
        if (c > 0) {
            items.push_back({weight[i] * c, value[i] * c});
        }
    }

    // Стандартен 0/1 Knapsack
    vector<int> dp(W + 1, 0);
    for (auto [w, v] : items) {
        for (int i = W; i >= w; i--) {
            dp[i] = max(dp[i], dp[i - w] + v);
        }
    }

    return dp[W];
}

Knapsack с точна сума:

Понякога се иска да намерим начини да запълним раницата с точно определено тегло:

int exactKnapsack(int target, vector<int>& coins) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1; // Един начин да направим 0

    for (int coin : coins) {
        for (int i = coin; i <= target; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[target];
}

🕸️ ДП върху профил (Broken Profile DP) - Детайли

Използва се за запълване на мрежи \(N \times M\) (където \(N\) е малко). Строим мрежата клетка по клетка. Профилът е границата между обработените и необработените клетки. - Ако местим ред по ред, профилът е състоянието на текущия ред (битова маска). - Ако местим клетка по клетка, профилът включва \(N\) бита (части от текущия и следващия ред).

Класически пример: Покриване с домина

Задача: По колко начина можем да покрием мрежа \(N \times M\) с домина \(1 \times 2\)?

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 11;
const int MAXM = 1001;
long long dp[MAXM][1 << MAXN];
int n, m;

// Генерира всички валидни преходи от маска към следваща маска
void gen(int pos, int cur_mask, int next_mask, int col, long long val) {
    if (pos == n) {
        dp[col + 1][next_mask] += val;
        return;
    }

    if (cur_mask & (1 << pos)) {
        // Вече запълнена - продължаваме
        gen(pos + 1, cur_mask, next_mask, col, val);
    } else {
        // Опция 1: Вертикално домино
        gen(pos + 1, cur_mask | (1 << pos), next_mask | (1 << pos), col, val);

        // Опция 2: Хоризонтално домино (ако има място)
        if (pos + 1 < n && !(cur_mask & (1 << (pos + 1)))) {
            gen(pos + 2, cur_mask | (1 << pos) | (1 << (pos + 1)), 
                next_mask, col, val);
        }
    }
}

long long countTilings(int N, int M) {
    n = N; m = M;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int col = 0; col < m; col++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[col][mask] > 0) {
                gen(0, mask, 0, col, dp[col][mask]);
            }
        }
    }

    return dp[m][0];
}

int main() {
    cout << "Начини за покриване 3x4: " 
         << countTilings(3, 4) << endl;
    return 0;
}

Сложност: \(O(M \cdot 2^N \cdot N)\) където \(N \leq 10\).

🎯 Практически задачи

  1. CSES: Dice Combinations - Базово ДП
  2. CSES: Counting Towers - Profile DP
  3. Codeforces 1073E - Digit DP с ограничение за различни цифри
  4. CSES: Tree Distances II - Tree DP за сума на разстояния
  5. AtCoder DP Contest - Колекция от 26 ДП задачи

💡 Съвети и добри практики

  1. Дефинирайте състоянието ясно: Запишете си какво означава всеки параметър.
  2. Проверете границите: Какви са базовите случаи?
  3. Мемоизация срещу табулация: Мемоизацията (top-down) е по-интуитивна, но табулацията (bottom-up) често е по-бърза.
  4. Оптимизация на паметта: Ако dp[i] зависи само от dp[i-1], използвайте два масива вместо цяла матрица.
  5. Следете за препълване: При големи числа използвайте long long или модулна аритметика.

🏁 Заключение

Динамичното програмиране е изкуство. Най-важната стъпка е да дефинирате състояние, което съдържа достатъчно информация за бъдещите решения, но е минимално като размер. Винаги проверявайте за припокриващи се подзадачи! Практикувайте редовно с различни типове задачи, за да развиете интуиция кога и как да прилагате ДП.