#include<iostream>
using namespace std;
/*
給定n個(gè)矩陣{A1,A2,...,An}，其中Ai與Ai+1是可乘的，i = 1,2...,n-1。我們
要計(jì)算出這n個(gè)矩陣的連乘積A1A2...An。
*/
/*
分析最優(yōu)子結(jié)構(gòu)：
設(shè)計(jì)求解具體問題的動(dòng)態(tài)規(guī)劃算法的第一步是刻畫該問題的
最優(yōu)結(jié)構(gòu)的特征。為方便，將矩陣連乘AiAi+1...Aj簡記為A[i:j]。
我們來看計(jì)算A[1:n]的一個(gè)最優(yōu)次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開
，1<=k<n，則完全加括號方式為((A1...Ak)(Ak+1...An))。依此順序
，我們先計(jì)算A[1:k]和A[k+1:n]，然后將計(jì)算結(jié)果相乘得到A[1:n].

問題的關(guān)鍵特征是：計(jì)算A[1:n]的一個(gè)最優(yōu)次序所包含的計(jì)算矩陣A[1:k]和A[k+1:n]的次序也是最
優(yōu)的。事實(shí)上，若有一個(gè)計(jì)算A[1:k]的次序需要的計(jì)算量更少，則用此次序替換原來的計(jì)算A[1:k]
的次序，得到的計(jì)算A[1:n]的次序需要的計(jì)算量將比最優(yōu)次序所需要的計(jì)算量更少，這是一個(gè)矛盾。

因此，矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。
一個(gè)問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，是該問題能夠用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。
*/

/*
建立遞歸關(guān)系：
設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法的第二步是遞歸地定義最優(yōu)值。對于矩陣連乘積的最優(yōu)計(jì)算次序
問題，設(shè)計(jì)算A[i:j]，1<=i<=j<=n，所需的最少數(shù)乘次數(shù)為m[i][j]，則原問題的最優(yōu)
值為m[1][n]。
m[i][j]可以遞歸地定義為：
m[i][j]=0 (i==j)
m[i][j]=min{m[i][k] + m[k+1][j] + Pi-1PmPj}i<=k<j

若將對應(yīng)于m[i][j]的斷開位置k記為s[i][j]，在計(jì)算出最優(yōu)值
m[i][j]后，可遞歸地由s[i][j]構(gòu)造出相應(yīng)的最優(yōu)解
*/

/*
計(jì)算最優(yōu)值
根據(jù)計(jì)算m[i][j]的遞歸式，容易寫一個(gè)遞歸算法來計(jì)算m[1][n]
在遞歸計(jì)算的過程中，不同的子問題的個(gè)數(shù)只有O(n^2)個(gè)。事實(shí)上，對于1<=i<=j<=n不同的
有序?qū)?i,j)對應(yīng)于不同的子問題。因此不同子問題的個(gè)數(shù)最多只有(n,2)+n=O(n^2)個(gè)。
遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著
特征。

用動(dòng)態(tài)規(guī)劃算法解此問題時(shí)，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，
保存已經(jīng)解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡單查一下，從而
避免了大量的重復(fù)計(jì)算，最終得到多項(xiàng)式的時(shí)間算法。下面所給出的計(jì)算m[i][j]的動(dòng)態(tài)規(guī)劃算法
中，輸入?yún)?shù){p0,p1,...,pn}存儲(chǔ)于數(shù)組p中。算法除了輸出最優(yōu)數(shù)組m外，還輸出記錄最優(yōu)斷開
位置的數(shù)組s
*/

//p數(shù)組記錄的是每個(gè)矩陣的維數(shù)
void MatrixChain( int *p,int n,int **m,int **s )
{
	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 )
		//是為了只計(jì)算i:j的最小乘法次數(shù)，其中要求i<j，因?yàn)閕>j沒意義
		{
			int j = i + r - 1;
			m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
			s[i][j] = i;
			cout<<s[i][j]<<" "<<endl;
			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;
				}
			}
		}
	}
}

/*
構(gòu)造最優(yōu)解
動(dòng)態(tài)規(guī)劃算法的第4步是構(gòu)造問題的一個(gè)最優(yōu)解。算法MatrixChain只是計(jì)算出了最優(yōu)
值，并位給出最優(yōu)解。

MatrixChain已記錄了構(gòu)造一個(gè)最優(yōu)解所需要的全部信息。事實(shí)上，s[i][j]中的數(shù)k告訴我們
計(jì)算矩陣鏈A[i:j]的最佳方式應(yīng)在矩陣Ak和Ak+1之間斷開，即最優(yōu)的加括號方式應(yīng)為(A[i:k]
)(A[k+1:j])。因此，動(dòng)s[1][n]中記錄的信息可知計(jì)算A[1:n]的最優(yōu)加括號方式為
(A[1:s[1][n])(A[s[1][n]+1:n)。
*/

/*
下面的算法Traceback按算法MaxtrixChain計(jì)算出的斷點(diǎn)矩陣s
指示的加括號方式輸出計(jì)算A[i:j]的最優(yōu)計(jì)算順序。
*/

void Trackback( int i, int j, int **s )
{
	if ( i == j )
	{
		return;
	}
	Trackback( i, s[i][j], s );
	Trackback( s[i][j] + 1, j, s );
	cout<<"i is : "<<i<<endl;
	cout<<"j is : "<<j<<endl;
	cout<<"Multiply A["<<i<<":"<<s[i][j]<<"]"<<endl;
	cout<<"and A["<<(s[i][j]+1)<<":"<<j<<"]"<<endl;
	
}

int main()
{
	int n = 6;
	int *p = new int[7];
	p[1] = 35;
	p[2] = 15;
	p[3] = 5;
	p[4] = 10;
	p[5] = 20;
	p[6] = 25;

	int **m = new int*[7];
	int **s = new int*[7];
	for( int i = 0; i < 7; ++i )
	{
		m[i] = new int[7];
		s[i] = new int[7];
		for( int j = 0; j < 7; ++j )
		{
			m[i][j] = 0;
			s[i][j] = 0;
		}
	}

	MatrixChain( p,6,m,s );
	for( int t = 0; t < 7; ++t )
	{
		for( int q = 0; q < 7; ++q )
		{
			cout<<s[t][q]<<" ";
		}
		cout<<endl;
	}
	Trackback( 1, 6, s );

	return 0;
}