【实验内容】

输入：矩阵链Ai…j的输入为向量P=<Pi-1, Pi, …, Pj>，其中：1<=i<=j<=n.

输出：计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。

要求采用迭代方法进行程序设计，并设计备忘录和标记函数表。

建议参考P59中算法3.2的伪码进行编程，要求应用教材P59中3.2.4给出例子中的数据进行算法验证。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
//输入：矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>，其中：1<=i<=j<=n.
//输出：计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。
const int N = 101;
int m[N][N], s[N][N];
int a[] = {30, 35, 15, 5, 10, 20};

void MatrixChain(int a[N], int n)
{
	for(int i=1; i<=n; i++)
		m[i][i] = 0;
		
	for(int r=2; r<=n; r++)
	{
		for(int i=1; i<= n-r+1; i++)
		{
			int j = i+r-1;
			m[i][j] = m[i+1][j] + a[i-1]*a[i]*a[j];
			s[i][j] = i;
			
			for(int k=i; k<=j-1; k++)
			{
				int t = m[i][k] + m[k+1][j] + a[i-1]*a[k]*a[j];
				if(t < m[i][j])
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

int main()
{
 	MatrixChain(a, 6);
 	cout << "The number of least multiplication operations:" << endl;
 	cout << m[1][5] << endl;
 	cout << "Position of the last operation:" << endl;
 	cout << s[1][5] << endl;
 	cout << "array s:" << endl;
 	for(int i=1; i<=5; i++)
 	{
 		for(int j=1; j<=5; j++)
 		{
 			cout << s[i][j] << ' ';
		}
		cout << endl;
	 }
 	return 0;
}