矩阵连乘问题

1. 分析与动态方程:

分析如下：

        要计算n个矩阵，A1，A2，…，An，可利用动态规划进行解决。

        设m[1][n]为A1，A2，…，An连乘的计算量；

        此问题符合最优子结构问题，即：当[A1，A2，…，An]构成最优的解，连乘次数最少，即m[1][n]最小，则其子问题[A1，A2，…，Ak]与[Ak+1，A2，…，An]（k为常数，1<=k

        即m[1][n]=m[1][k]+m[k+1][n]+ P(1_) P(k)P(n)；最小时m[1][k]最小，m[k+1][n]最小；

k表示在第k个元素后面断开,、

P(i)表示第i个元素的列数；P(i_)表示第i个元素的行数

所以有：

P(1_ )表示第1个元素的行数

P(k)表示第k个元素的列数

P(n)表示第n个元素的列数

证明如下：

 反证法：若[A1，A2，…，Ak]不是最优解，则可以找到另外的次序m_[1][k]，使其乘法计算量少于[A1，A2，…，Ak]的乘法计算量m[1][k]

        则有m_[1][n] < m[1][n];

        所以m[1][n]不是最小值

这与m[1][n]为最小值，[A1，A2，…，An]构成最优的解矛盾，故此不成立，原结论成立。

        2. 求解动态规划方程：

当只有一个矩阵时，连乘次数m[1][1]=0;

m[1][2] =  m[1][1]+m[2][2]+ P(1,k) P(k)P(k+1,n)

        =  0+0+ P(1,k) P(k)P(k+1,n)

        =  P(1,k) P(k)P(k+1,n)

m[1][n]= m[1][n]=m[1][k]+m[k+1][n]+ P(1_) P(k)P(n)；

动态规划方程为：

程序截图为：

        3. 源代码及注释：

#include
#include
#include
using namespace std;

void MatrixChain(vector &p, int n, vector> &m, vector> &s) {
	for (int i = 0; i < n; i++)	//规模为1时，i=j,计算量m[i][j]=m[i][i]=0;
		m[i][i] = 0;
	for (int r = 2; r <= n; r++)	//规模为r时，i>& s,string &order)
{
	if (i == j)       //回归条件
	{
		order.append("A");
		order.append(to_string(i));
	}
	else       //按照最佳断点一分为二，接着继续递归
	{
		order.append("(");
		Traceback(i, s[i][j], s,order);
		Traceback(s[i][j] + 1, j, s,order);
		order.append(")");
	}
}

void creative_matrix() {

	int n;
	string order;					 //构造连乘矩阵的输出形式
	string out("n");						 //构造最后输出
	for (int i = 1; cin >> n;i++)	 //当输入ctrl+z时，结束输入
	{
		order = "";					 //初始化空串
		vectorp(n + 1);
		vector>m(n);
		vector>s(n);
		for (int i = 0; i < n; i++)	//构造准备数组
		{
			cin >> p[i];
			m[i].resize(n);
			s[i].resize(n);
		}
		cin >> p[n];

		MatrixChain(p, n, m, s);	 //递归求解

		Traceback(0, n - 1, s, order);	  //递归求解
		order.erase(order.begin());	      //去头括号
		order.erase(order.end() - 1);	  //去尾括号
		out += "Case" + to_string(i) + 'n'
			+  to_string(m[0][n - 1]) + "  " + order + 'n';	//字符串拼接
	}
	cout << out;
}

int main() {
	cout << "请输入数据，按ctrl+z结束输入:" << endl;
	creative_matrix();
	return 0;
}