Оптимальне множення матриць
Маючи дві матриці A і B, ми можемо обчислити матрицю C = AB за стандартними правилами множення матриць:
Кількість стовпців у матриці A повинна дорівнювати кількості рядків у матриці B. Нехай матриця A має розмір m × n, а матриця B — розмір n × p. Тоді матриця C матиме розмір m × p, і для її обчислення потрібно виконати m * n * p множень.
Наприклад, якщо A має розмір 10 × 20, а B — розмір 20 × 15, то для обчислення матриці C потрібно виконати 10 × 20 × 15 = 3000 множень.
Перемножувати кілька матриць можна різними способами. Наприклад, якщо у нас є матриці X, Y і Z, то обчислити XYZ можна як (XY)Z або X(YZ). Нехай X має розмір 5 × 10, Y — розмір 10 × 20, а Z — розмір 20 × 35.
Порахуємо кількість множень, необхідних для перемноження трьох матриць у кожному з цих двох випадків:
(XY)Z
5 × 20 × 10 = 1000 множень для обчислення матриці (XY), що має розмір 5 × 20.
Потім 5 × 35 × 20 = 3500 множень для отримання кінцевого результату.
Загальна кількість множень: 4500.
X(YZ)
10 × 35 × 20 = 7000 множень для обчислення матриці (YZ), що має розмір 10 × 35.
Потім 5 × 35 × 10 множень для отримання кінцевого результату.
Загальна кількість множень: 8750.
Очевидно, що при обчисленні (XY)Z потрібно менше множень.
За заданою послідовністю перемножуваних матриць потрібно знайти оптимальний порядок їх множення. Оптимальним вважається такий порядок, при якому кількість елементарних множень є мінімальною.
Вхідні дані
Перший рядок містить кількість n (n ≤ 10) матриць, які потрібно перемножити. Далі йдуть n пар цілих чисел, що описують кількість рядків і стовпців кожної матриці, у порядку їх множення.
Вихідні дані
Виведіть мінімальну кількість множень, необхідну для перемноження всіх матриць.