Оптимальное перемножение матриц

1. Идея

Нужно найти, как расставить скобки в произведении A_1 · A_2 · ... · A_n, чтобы число скалярных умножений было минимальным.

Ключевая мысль: если рассматривать не всю цепочку сразу, а любой отрезок матриц от A_l до A_r, то оптимальный ответ для этого отрезка можно выразить через ответы для более коротких отрезков.

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

2. Наблюдения

Наблюдение 1. Одна матрица ничего не стоит

Если отрезок состоит из одной матрицы, например только A_i, то перемножать ничего не нужно. Значит:

• стоимость равна 0.

Наблюдение 2. Последнее действие всегда разбивает отрезок на две части

Пусть мы хотим оптимально перемножить матрицы от A_l до A_r.

В самом конце мы обязательно перемножаем:

• результат левой части A_l ... A_k,
• и результат правой части A_{k+1} ... A_r

для некоторого k, где l <= k < r.

Значит, если мы выбрали место последнего разбиения k, то общая стоимость равна:

• стоимости оптимального перемножения A_l ... A_k,
• плюс стоимости оптимального перемножения A_{k+1} ... A_r,
• плюс стоимость перемножения двух полученных результатов.

Наблюдение 3. Размеры результирующих матриц известны

По условию:

• A_i имеет размер p_{i-1} x p_i.

Тогда произведение A_l ... A_k будет иметь размер p_{l-1} x p_k, а произведение A_{k+1} ... A_r — размер p_k x p_r.

Значит, их перемножение стоит:

p[l - 1] * p[k] * p[r]

3. Алгоритм

Обозначим dp[l][r] — минимальное число скалярных умножений, нужное для вычисления произведения A_l ... A_r.

База

Если l == r, то:

• dp[l][r] = 0

Переход

Для каждого отрезка l..r длины хотя бы 2 переберём позицию последнего разбиения k:

dp[l][r] = min(dp[l][k] + dp[k+1][r] + p[l-1] * p[k] * p[r])

где k пробегает все значения от l до r - 1.

Порядок вычисления

Так как dp[l][r] зависит от более коротких отрезков, нужно идти по возрастанию длины:

• сначала длина 2,
• потом 3,
• ...
• до n.

Что будет ответом

Нужно перемножить всю цепочку от A_1 до A_n, поэтому ответ:

• dp[1][n]

4. Почему это работает

Докажем корректность идеи.

Рассмотрим некоторый отрезок матриц A_l ... A_r.

Если l == r, то это одна матрица, и стоимость действительно 0. База верна.

Теперь пусть l < r. Любой способ расставить скобки на этом отрезке имеет последнее действие: в конце перемножаются два уже готовых результата. Значит, существует такое k, что:

• слева вычисляется A_l ... A_k,
• справа вычисляется A_{k+1} ... A_r.

Если этот способ оптимален, то и левая, и правая части должны быть вычислены оптимально. Иначе можно было бы заменить одну из частей на более дешёвую и получить ещё лучший общий ответ, что противоречит оптимальности.

Поэтому для фиксированного k лучшая стоимость равна:

dp[l][k] + dp[k+1][r] + p[l-1] * p[k] * p[r]

Остаётся выбрать наилучшее k. Именно это и делает переход динамики.

Так как мы перебираем все возможные разбиения и для каждого используем уже найденные оптимальные ответы для меньших отрезков, значение dp[l][r] получается правильным.

Следовательно, правильным будет и итоговый ответ dp[1][n].

5. Сложность

Пусть n — число матриц.

• Состояний dp[l][r] всего O(n^2).
• Для каждого состояния перебираются все k, то есть до O(n) вариантов.

Итоговая сложность:

• O(n^3)

Память:

• O(n^2)

При n <= 300 такой алгоритм подходит.

6. Код на C++17

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> p(n + 1);
    for (int i = 0; i <= n; i++) {
        cin >> p[i];
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    const long long INF = numeric_limits<long long>::max();

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            for (int k = l; k < r; k++) {
                long long cost = dp[l][k] + dp[k + 1][r] + p[l - 1] * p[k] * p[r];
                if (cost < dp[l][r]) {
                    dp[l][r] = cost;
                }
            }
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
p = list(map(int, input().split()))

dp = [[0] * (n + 1) for _ in range(n + 1)]

for length in range(2, n + 1):
    for l in range(1, n - length + 2):
        r = l + length - 1
        best = 10**30
        for k in range(l, r):
            cost = dp[l][k] + dp[k + 1][r] + p[l - 1] * p[k] * p[r]
            if cost < best:
                best = cost
        dp[l][r] = best

print(dp[1][n])