heihei12305

问题描述：给定n个矩阵{A1,A2,A3.....An},其中Ai与Ai+1是可乘的，i=1,2,3....n-1,考察这n个矩阵的连乘积
若A是一个 p* q 矩阵，B是一个 q* r 矩阵，则其乘积C = A* B 是一个 p* r 矩阵，主要运算量是三重循环，共需要p* q* r次数乘。


动态规划核心公式 m[i][j] = min{m[i][k]+m[k+1][j]+Pi-1*PkPj } i<j i<=k<j

许多子问题被重复计算多次，这是该问题可用动态规划求解的一显著特征

	void MatrixChain(vector<int> &p,int n,vector<vector<int> > &m,vector<vector<int> > &s)
	{
		for(int i  =1;i<=n;i++)
		{
			m[i][i] = 0;
		}
		for(int r = 2;r<=n;r++)//r为 i 和 j之间的距离！！！
		{
			for(int i = 1;i<=n-r+1;i++)//这个循环条件要注意哦!，也就是 j<n 啦
			{
				int j = i+r-1;
				m[i][j] = m[i-1][j] + p[i-1]*p[i]*p[j];
				s[i][j] = i;
				for(int k = i+1;k<j;k++)
				{
					int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
					if(t<m[i][j])
					{
						m[i][j] = t;
						s[i][j] = k;//中断点记录下来了
					}
				}
			}
		}
	}
	
	

struct symbol
{
	int leftParent = 0, rightParent = 0;
};
//获取符号位置
void getExpression(int start, int end, vector<symbol> &symbols, vector<vector<int>> &s)
{
	if (start == end) {
		return;
	}
	else
	{
		symbols[start].leftParent++;
		symbols[end + 1].rightParent++;
	}
	if (start + 1 == end) {
		return;
	}
	int posi = s[start][end];
	getExpression(start, posi, symbols,form);
	getExpression(posi + 1, end, symbols,form);
}
//输出表达式
void Traceback(vector<symbol> symbols, vector<vector<cell>> &s,int n) {
	getExpression(0, n - 1, symbols, s);
	for (int i = 0; i < n; i++)
	{
		int l = symbols[i].leftParent, r = symbols[i].rightParent;
		while (r--)
		{
			cout << ")";
		}
		while (l--)
		{
			cout << "(";
		}
		cout << " " << 'A'  << i+1 << " ";
	}
	int  r = symbols[n].rightParent;
	while (r--)
	{
		cout << ")";
	}
}