Оптимизации динамического программирования

Divide & Conquer-оптимизация

Решается задача «Разделить массив на partCount частей, минимизировав нечто». Паттерн — двумерная динамика, позиция в массиве + число.

Базовое решение за O(N^2 * P):

vector<vector<long long>> res(a.size() + 1, vector<long long>(partCount + 1, 1e18));
res[0][0] = 0;

for (int size = 0; size <= a.size(); size++) {
    for (int parts = 1; parts <= partCount; parts++) {
        for (int partSize = 1; partSize <= size; partSize++) {
            long long partPrice = getPartPrice(size - partSize, size - 1);
            res[size][parts] = min(res[size][parts], res[size - partSize][parts - 1] + partPrice);
        }
    }
}

return res[a.size()][partCount];

Поменяем порядок индексов и будем перебирать prevSize вместо partSize:

vector<vector<long long>> res(partCount + 1, vector<long long>(a.size() + 1, 1e18));
res[0][0] = 0;

for (int parts = 1; parts <= partCount; parts++) {
    for (int size = 0; size <= a.size(); size++) {
        for (int prevSize = 0; prevSize < size; prevSize++) {
            long long partPrice = getPartPrice(prevSize, size - 1);
            res[parts][size] = min(res[parts][size], res[parts - 1][prevSize] + partPrice);
        }
    }
}

return res[partCount][a.size()];

Вынесем расчёт строки для фиксированного parts в функцию:

void calc(vector<vector<long long>> &res, int parts, vector<long long> &p) {
    for (int size = 0; size < res[0].size(); size++) {
        for (int prevSize = 0; prevSize < size; prevSize++) {
            long long partPrice = getPartPrice(prevSize, size - 1);
            res[parts][size] = min(res[parts][size], res[parts - 1][prevSize] + partPrice);
        }
    }
}

vector<vector<long long>> res(partCount + 1, vector<long long>(a.size() + 1, 1e18));
res[0][0] = 0;

for (int parts = 1; parts <= partCount; parts++)
    calc(res, parts, p);

return res[partCount][a.size()];

Внутри функции вместо цикла по size сделаем рекурсию:

void rec(vector<vector<long long>> &res, int parts, int sizeL, int sizeR, vector<long long> &p) {
    if (sizeL > sizeR)
        return;

    int size = sizeL + (sizeR - sizeL) / 2;

    for (int prevSize = 0; prevSize < size; prevSize++) {
        long long partPrice = getPartPrice(prevSize, size - 1);
        res[parts][size] = min(res[parts][size], res[parts - 1][prevSize] + partPrice);
    }

    rec(res, parts, sizeL, size - 1, p);
    rec(res, parts, size + 1, sizeR, p);
}

vector<vector<long long>> res(partCount + 1, vector<long long>(a.size() + 1, 1e18));
res[0][0] = 0;

for (int parts = 1; parts <= partCount; parts++)
    rec(res, parts, 0, a.size(), p);

return res[partCount][a.size()];

В рекурсии будем сохранять лучший prevSize:

void rec(vector<vector<long long>> &res, int parts, int sizeL, int sizeR, vector<long long> &p) {
    if (sizeL > sizeR)
        return;

    int size = sizeL + (sizeR - sizeL) / 2;
    int bestPrevSize = 0;

    for (int prevSize = 0; prevSize < size; prevSize++) {
        long long partPrice = getPartPrice(prevSize, size - 1);
        if (res[parts][size] > res[parts - 1][prevSize] + partPrice) {
            res[parts][size] = res[parts - 1][prevSize] + partPrice;
            bestPrevSize = prevSize;
        }
    }

    rec(res, parts, sizeL, size - 1, p);
    rec(res, parts, size + 1, sizeR, p);
}

vector<vector<long long>> res(partCount + 1, vector<long long>(a.size() + 1, 1e18));
res[0][0] = 0;

for (int parts = 1; parts <= partCount; parts++)
    rec(res, parts, 0, a.size(), p);

return res[partCount][a.size()];

Заметим, что в рекурсивных вызовах можно перебирать prevSize только до bestPrevSize или только от bestPrevSize.

Сложность становится равной O(NlogN * P).

void rec(vector<vector<long long>> &res, int parts, int sizeL, int sizeR, int prevSizeL, int prevSizeR, vector<long long> &p) {
    if (sizeL > sizeR)
        return;

    int size = sizeL + (sizeR - sizeL) / 2;
    int bestPrevSize = prevSizeL;

    for (int prevSize = prevSizeL; prevSize <= prevSizeR && prevSize < size; prevSize++) {
        long long partPrice = getPartPrice(p, prevSize, size - 1);
        if (res[parts][size] > res[parts - 1][prevSize] + partPrice) {
            res[parts][size] = res[parts - 1][prevSize] + partPrice;
            bestPrevSize = prevSize;
        }
    }

    rec(res, parts, sizeL, size - 1, prevSizeL, bestPrevSize, p);
    rec(res, parts, size + 1, sizeR, bestPrevSize, prevSizeR, p);
}

vector<vector<long long>> res(partCount + 1, vector<long long>(a.size() + 1, 1e18));
res[0][0] = 0;

for (int parts = 1; parts <= partCount; parts++)
    rec(res, parts, 0, a.size(), 0, a.size(), p);

return res[partCount][a.size()];

• algorithmica.org — Пересчёт динамики по слоям. Разделяй-и-властвуй
• algocode.ru — Divide & Conquer-оптимизация
• cp-algorithms.com — Divide and Conquer DP
• Nasser M. — DP Divide and Conquer Optimization
• robert1003.github.io — Divide and Conquer DP
• usaco.guide — Divide & Conquer DP
• Xiao J. — Divide and Conquer Optimization

Ссылки

Теория:

• algorithmica.org — Пересчёт динамики по слоям
• algocode.ru — Оптимизации динамики: 1, 2, 3, 4, 5
• codeforces.com — Dynamic Programming Optimizations
• codeforces.com — Non-trivial DP Tricks and Techniques
• cp-algorithms.com — Knuth's Optimization
• usaco.guide — Additional DP Optimizations and Techniques
• Erickson J. Advanced Dynamic Programming
• Xiao J. Convex Hull Trick, Knuth's Optimization
• Ахмедов М. Dynamic programming optimizations
• Копелиович С. Лекция по динамике (ЗКШ 2017)