算法學習之動态規劃（求矩陣連乘最小相乘次數）

 基本思想：動态規劃算法與分治法類似，其基本思想是将帶求解的問題劃分成若幹個獨立子問題，根據求得子問題的解合并而得到原問題的解。而動态規劃劃分的子問題往往不是互相獨立的，是以若采用同分治法相同的求解問題的方法會導緻大量的子問題被重複計算，為了避免這種情況發生，我們可以用一個表來記錄我們求得的子問題的解，無論該子問題的解以後是否會用到，隻要被計算，就将其填入表中。這便是動态規劃的基本思想。

求解的基本步驟：

（1）找出最優解的性質，并刻畫其結構特征。

（2）遞歸的定義最優值。

（3）以自底向上的方式計算出最優值。

（4）根據計算最優值時得到的資訊，構造最優解。

#include <iostream>
//數組p存儲連乘矩陣的維數
int p[] = { 30, 35, 35, 15, 15, 5, 5, 10, 10, 20, 20, 25 };
int pcount = sizeof(p) / sizeof(*p);
//二維數組m存放所有子問題的最優值
int m[6][6];
//二維數組s存放斷開的位置k
int s[6][6];
//用于列印二維數組
void debug(int array[][6]);
//預初始化二維數組
void initialization(int array[][6]);
//列印最優解的構成
void Traceback(int i, int j, int array[][6]);
//根據自底向上的方式計算所有子問題最優值
void MatrixChain(int *p, int n, int m[][6], int s[][6])
{
	initialization(m);	
	initialization(s);	
	//注意n/2得到的是相乘矩陣的個數	
	for (int i = 0; i < n/2; i++) m[i][i] = 0;    //單個矩陣最優值為0	
	//外層循環，從矩陣A1-A5依次計算矩陣鍊長度為2,3,4,5	
	for (int r = 1; r < n/2;r++)	
		//内層循環,計算矩陣鍊長度為x(x可能為2,3,4,5)的所有值（例如：若x=2，
		//則計算m[1][2],m[2][3],m[3][4],m[4][5],m[5][6]）	
	for (int i = 0; i < n/2 - r; i++)
		//随矩陣鍊長度x增加,i的最大值與(n/2-r)	                                 
		//構成對應關系	
	{		
		int j = i + r;							//列數j取決于矩陣鍊長度和行數i		
		m[i][j] = m[i + 1][j] + p[2 * i] * p[2 * i + 1] * p[j * 2 + 1];		
		//這裡先求出一個基本解，以A0矩陣劃分（A[0]*A[1:5]）		
		//std::cout << "m"<<"["<<i<<"]"<<"["<<j<<"]"<<m[i][j] << std::endl;		
		s[i][j] = i;							//儲存劃分的位置，Trackback求最優解用到		
		for (int k = i + 1; k < j; k++)			//對每個可能劃分的位置進行檢索		
		{			
			int t = m[i][k] + m[k + 1][j] + p[2 * i] * p[2 * k + 1] * p[2 * j + 1];     //求最優值的遞推式			
		//如果計算得到的值比基本解更優，那麼替換原來的最優值和劃分位置			
		if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}		
		}	
	}

}
void debug(int array[][6])
{
	for (int i = 0; i < 6; i++)	
	{
		for (int j = 0; j < 6; j++)			
		std::cout << array[i][j] << " ";		
		std::cout << std::endl;	
	}
}

void initialization(int array[][6])
{	
	for (int i = 0; i < 6; i++)	
		for (int j = 0; j < 6; j++)		
		array[i][j] = -1;
}

void Traceback(int i, int j, int array[][6])
{	
	using std::cout;	
	using std::endl;	
	if (i == j) return;	
	Traceback(i, array[i][j], array);	
	Traceback(array[i][j] + 1, j, array);	
	cout << "Multiply A" << i << "," << array[i][j];	
	cout << " and A" << (array[i][j] + 1) << "," << j << endl;
}

//一小段測試程式，不懂請盡可能多調試以便了解。
int main()
{	
	MatrixChain(p, pcount, m, s);	
	debug(m);	
	//debug(s);	
	Traceback(1, 5, s);	
	return 0;
}