Interval DP: как реализовать задачу о перемножении цепочки матриц за O(n³)?
Дана последовательность размеров матриц p[0..n] (матрица $i$ имеет размер p[i-1] × p[i]). Нужно расставить скобки так, чтобы минимизировать число скалярных умножений. Понимаю, что это ДП на отрезках, но путаюсь, что брать за состояние и как перебирать точку разбиения.
2 ответа
Это эталонный interval DP. Состояние dp[i][j] = минимальная стоимость перемножить матрицы с $i$ по $j$ включительно. Перебираем точку разбиения $k$ ($i \le k < j$): сначала перемножаем [i..k], потом [k+1..j], потом две полученные матрицы.
Цена финального умножения двух блоков: p[i-1] * p[k] * p[j].
int n; // число матриц
vector<long long> p(n + 1); // p[0..n], читаем заранее
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
for (int len = 2; len <= n; ++len) // длина отрезка
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
dp[i][j] = LLONG_MAX;
for (int k = i; k < j; ++k) {
long long cost = dp[i][k] + dp[k + 1][j]
+ p[i - 1] * p[k] * p[j];
dp[i][j] = min(dp[i][j], cost);
}
}
// ответ dp[1][n]
Ключевой порядок — по возрастанию длины отрезка, чтобы dp[i][k] и dp[k+1][j] (более короткие) уже были посчитаны.
Сложность: $O(n^2)$ состояний $\times$ $O(n)$ на перебор $k$ → $O(n^3)$ времени, $O(n^2)$ памяти. Произведение трёх размеров переполняет int — long long обязателен.
Замечу про общий шаблон interval DP: почти всегда это «перебор точки/последнего действия на отрезке» + база на отрезках длины 1 (или 0). Сюда же ложатся: оптимальная триангуляция выпуклого многоугольника (вместо матриц — треугольники, цена = периметр/площадь), «лопающиеся шарики» (Burst Balloons), удаление палиндромных подстрок. Меняется только формула цены cost, каркас тот же.
Если $n$ большой (до нескольких тысяч) и выполняется неравенство четырёхугольника, $O(n^3)$ ускоряется до $O(n^2)$ оптимизацией Кнута — но это отдельная тема.