C ++程序使用动态编程来执行最佳的并行化
这是一个C++程序，用于使用动态编程来执行最佳Paranthesization。
算法
Begin
Take the length n and dimension of matrix as input.
MatrixChain() to find out minimum multiplications:
Arguments:
a[i][j]=Minimum number of scalar multiplications needed to
compute the matrix A[i]A[i+1]...A[j] = A[i..j] where dimension of A[i] is p[i-1] x p[i].
a[i][j] means cost is zero when multiplying one matrix.
L is chain length.
m = cost / scalar multiplications.
Body of the function:
for i = 1 to n-1
Initialize a[i][i] = 0
for L = 2 to n-1
for i = 1 to n - L + 1
j = i + L - 1
a[i][j] = INT_MAX
for k = i to j - 1
m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
if (m < a[i][j])
a[i][j] = m
b[i][j] = k
return a[1][n - 1]
End示例
#include<limits.h>
#include<iostream>
using namespace std;
int MatrixChain(int p[], int n) {
int a[n][n];
int b[n][n];
int i, j, k, L, m;
for (i = 1; i < n; i++)
a[i][i] = 0;
for (L = 2; L < n; L++) {
for (i = 1; i <= n - L + 1; i++) {
j = i + L - 1;
a[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++) {
m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
if (m < a[i][j]) {
a[i][j] = m;
b[i][j] = k;
}
}
}
}
return a[1][n - 1];
}
int main() {
cout << "输入长度：";
int n;
cin >> n;
int a[n];
cout << "Enter the dimensions: ";
for (int v = 0; v < n; ++v) {
cin >> a[v];
}
cout << "Minimum number of multiplications is: " <<
MatrixChain(a,n);
return 0;
}输出结果
输入长度：5 Enter the dimensions: 2 3 7 6 4 Minimum number of multiplications is: 174