矩阵链乘法
如果给出了矩阵链，则必须找到要相乘的正确矩阵序列的最小数目。
我们知道矩阵乘法是关联的，因此四个矩阵ABCD可以在这些序列中乘以A(BCD)，(AB)(CD)，(ABC)D，A(BC)D。像这些序列一样，我们的任务是找到可以有效相乘的顺序。
在给定的输入中，有一个数组说arr，其中包含arr[]={1,2,3,4}。这意味着矩阵的数量级为（1x2），（2x3），（3x4）。
输入输出
Input:
输入矩阵的阶数. {1, 2, 3, 4}. 这意味着矩阵是
{(1 x 2), (2 x 3), (3 x 4)}.
Output:
最少的运算次数需要将这三个矩阵相乘。这里的结果是18。算法
matOrder(array, n)
输入-矩数组表，列表中的矩阵数。
输出-矩阵乘法的最小数量。
Begin
定义大小为 n x n 的表 minMul，最初填充所有0
for length := 2 to n, do
fir i:=1 to n-length, do
j := i + length – 1
minMul[i, j] := ∞
for k := i to j-1, do
q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
if q < minMul[i, j], then minMul[i, j] := q
done
done
done
return minMul[1, n-1]
End示例
#include<iostream>
using namespace std;
int matOrder(int array[], int n) {
int minMul[n][n]; //存放所需标量乘法的数量
for (int i=1; i<n; i++)
minMul[i][i] = 0;
for (int length=2; length<n; length++) { //从2开始计算链的长度
for (int i=1; i<n-length+1; i++) {
int j = i+length-1;
minMul[i][j] = INT_MAX; //设为无穷大
for (int k=i; k<=j-1; k++) {
//每次存储的存储成本
int q = minMul[i][k] + minMul[k+1][j] + array[i- 1]*array[k]*array[j];
if (q < minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n-1];
}
int main() {
int arr[] = {1, 2, 3, 4};
int size = 4;
cout << "最小矩阵乘法数: " << matOrder(arr, size);
}输出结果
最小矩阵乘法数: 18