Интервальное ДП (matrix chain / склейка камней): как правильно задать порядок длин интервалов?
Решаю задачу про оптимальную склейку (matrix chain multiplication / merging stones) интервальным ДП dp[i][j]. Постоянно получаю мусор: то использую ещё не посчитанные подынтервалы, то ошибаюсь в базе. В каком порядке надо перебирать i, j, k и какая база?
2 ответа
Главное правило интервального ДП: dp[i][j] зависит от более коротких интервалов dp[i][k] и dp[k+1][j], поэтому внешний цикл должен идти по длине интервала, а не по i. Так все подынтервалы гарантированно посчитаны раньше.
// dp[i][j] — мин. стоимость склеить отрезок [i, j]
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int len = 2; len <= n; len++) // длина интервала
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = LLONG_MAX;
for (int k = i; k < j; k++) // точка деления
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, k, j));
}
long long ans = dp[0][n-1];
Сложность O(n³) время, O(n²) память. База: dp[i][i] = 0 (один элемент склеивать не надо) — задаётся инициализацией нулями. Грабли: k идёт от i до j-1 (правая часть начинается с k+1, не должна быть пустой); и cost(i,k,j) — стоимость слияния двух уже готовых кусков, считай её аккуратно (часто это prefix[j+1]-prefix[i]).
Если cost удовлетворяет неравенству четырёхугольника (а для сумм на отрезке оно выполняется), этот же O(n³) ускоряется до O(n²) оптимизацией Кнута через монотонность opt[i][j]. Но сначала добейся корректного O(n³): почти все WA здесь — это либо внешний цикл по i вместо длины (используешь непосчитанное), либо неверная граница k (включил k=j, и правый кусок стал пустым/некорректным). Сделай O(n³) рабочим и проверенным, и только потом оптимизируй.