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

Оптимизация Кнута (массив, число; N^2 * P → N^2)

Решается задача «Разделить массив на 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 = 1; 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 = 1; 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()];

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

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

for (int parts = 1; parts <= partCount; parts++) {
    for (int size = 1; size <= a.size(); size++) {
        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[parts][size] = prevSize;
            }
        }
    }
}

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

Условия применимости:

• Если делим на большее число частей тот же отрезок, последняя часть не должна начаться левее.
• Если делим на то же число частей больший отрезок, последняя часть не должна начаться левее.

bestPrevSize[parts - 1][size] <= bestPrevSize[parts][size]
bestPrevSize[parts][size] <= bestPrevSize[parts][size + 1]

Будем перебирать prevSize от bestPrevSize[parts - 1][size] до bestPrevSize[parts][size + 1]. Чтобы bestPrevSize[parts][size + 1] уже был вычислен, будем перебирать size по убыванию.

Сложность становится равной O(N^2).

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

for (int parts = 1; parts <= partCount; parts++) {
    for (int size = a.size(); size >= 1; size--) {
        int prevSizeL = bestPrevSize[parts - 1][size];
        int prevSizeR = size == a.size() ? size - 1 : min(size - 1, bestPrevSize[parts][size + 1]);

        for (int prevSize = prevSizeL; prevSize <= prevSizeR; 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[parts][size] = prevSize;
            }
        }
    }
}

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

• peltorator.org — Оптимизация Кнута — Яо
• algorithmica.org — Пересчёт динамики по слоям. Оптимизация Кнута

Оптимизация Кнута (подотрезок массива; N^3 → N^2)

Решается задача «Разделить массив на отдельные элементы (или собрать массив из отдельных элементов), минимизировав стоимость». Паттерн — двумерная динамика, LR-динамика.

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

vector<vector<long long>> res(a.size(), vector<long long>(a.size(), 1e18));

for (int i = 0; i < a.size(); i++)
    res[i][i] = 0;

for (int len = 2; len <= a.size(); len++) {
    for (int l = 0, r = len - 1; r < a.size(); l++, r++) {
        for (int m = l; m < r; m++) {
            long long price = getPrice(l, r);
            res[l][r] = min(res[l][r], res[l][m] + res[m + 1][r] + price);
        }
    }
}

return res[0][a.size() - 1];

Будем сохранять лучший m:

vector<vector<long long>> res(a.size(), vector<long long>(a.size(), 1e18));
vector<vector<int>> bestM(a.size(), vector<int>(a.size()));

for (int i = 0; i < a.size(); i++) {
    res[i][i] = 0;
    bestM[i][i] = i;
}

for (int len = 2; len <= a.size(); len++) {
    for (int l = 0, r = len - 1; r < a.size(); l++, r++) {
        for (int m = l; m < r; m++) {
            long long price = getPrice(l, r);
            if (res[l][r] > res[l][m] + res[m + 1][r] + price) {
                res[l][r] = res[l][m] + res[m + 1][r] + price;
                bestM[l][r] = m;
            }
        }
    }
}

return res[0][a.size() - 1];

Условия применимости:

• Если сдвигаем l правее, bestM не должен стать левее.
• Если сдвигаем r правее, bestM не должен стать левее.

bestM[l][r] <= bestM[l + 1][r]
bestM[l][r] <= bestM[l][r + 1] (или bestM[l][r - 1] <= bestM[l][r], что то же самое)

Будем перебирать m от bestM[l][r - 1] до bestM[l + 1][r].

Сложность становится равной O(N^2).

vector<vector<long long>> res(a.size(), vector<long long>(a.size(), 1e18));
vector<vector<int>> bestM(a.size(), vector<int>(a.size()));

for (int i = 0; i < a.size(); i++) {
    res[i][i] = 0;
    bestM[i][i] = i;
}

for (int len = 2; len <= a.size(); len++) {
    for (int l = 0, r = len - 1; r < a.size(); l++, r++) {
        int ml = bestM[l][r - 1];
        int mr = min(bestM[l + 1][r], r);

        for (int m = ml; m <= mr; m++) {
            long long price = getPrice(l, r);
            if (res[l][r] > res[l][m] + res[m + 1][r] + price) {
                res[l][r] = res[l][m] + res[m + 1][r] + price;
                bestM[l][r] = m;
            }
        }
    }
}

return res[0][a.size() - 1];

• peltorator.org — Оптимизация Кнута — Яо
• cp-algorithms.com — Knuth's Optimization (динамика по подотрезкам)
• robert1003.github.io — Knuth Optimization
• usaco.guide — Additional DP Optimizations and Techniques
• Xiao J. — Knuth's Optimization

Divide & Conquer-оптимизация (массив, число; N^2 * P → NlogN * P)

Решается задача «Разделить массив на 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 = 1; 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 = 1; 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 = 1; 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 — Пересчёт динамики по слоям. Разделяй-и-властвуй
• cp-algorithms.com — Divide and Conquer DP
• 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)