問題提出：
對於如下矩陣：
其中各矩陣A[i]下標為
計算其乘積的結果，以及我們需要計算其最小標量乘法次數。
問題分析：
首先我們需要明確的是何為標量：標量即為沒有方向的量，而有方向的量即為矢量。（嚴謹的定義自己百度去）
那麼標量乘法就變成了最基本的數字相乘。
其次對於兩個矩陣相乘，需滿足下示公式所示的形式：（左邊矩陣的列數與右邊矩陣的行數必須一致）
上述條件可從矩陣相乘的定義中看出：
在計算機，我們可以用一個二維數組來表示矩陣。
一個m行n列的矩陣與一個n行p列的矩陣相乘，會得到一個m行p列的矩陣，具體步驟如下：
其中第i行第j列位置上的數為第一個矩陣的第i行上的n個數與第二個矩陣第j列上的n個數對應相乘後所得的n個乘積之和。
下圖展示了一個簡單的例子：
從上圖我們可以得出兩個矩陣相乘城的次數，即為取得結果矩陣每個點所要做的標量乘法次數之和
而每個點的標量乘法次數為左邊矩陣的列數n，結果矩陣有m*p個點，那麼總數即為m*n*p；
另外我們也應該知道矩陣乘法符合乘法結合律，但不符合交換律；也就是說，我們可以為矩陣鏈乘設置括號，括號放置的位置不同，產生標量乘法的總量也是不一樣的哦，這一點我們必須明確，對這點不清楚的，可以自己舉個例子試試看。如果沒有這點，那這題就沒意義了。
前面科普了一大堆知識，現在進正題了：
對於矩陣鏈乘，我們可知道不同的括號化方案，會產生不同的計算代價；
算法導論書中指出了求完全括號化方案，所謂矩陣乘積鏈為完全括號化需滿足如下性質：
要麼是單一矩陣，要麼是兩個完全括號化的矩陣乘積鏈的積，且已加外括號。說實話這個定義讓人有點摸不著頭腦，待我仔細解釋下：
首先：該乘積鏈中只有一個矩陣，即單一矩陣，該乘積鏈必是完全括號化，且該矩陣外部不用加括號。
再者：必須是兩個括號化的矩陣鏈的乘積，我們可以把兩個括號化的矩陣鏈看作兩個結果矩陣（即兩個單一矩陣），該兩個矩陣相乘，並加上外括號把他們括住，即這種形式也叫著完全括號化的。
啰嗦了這麼多，感覺簡單的說法就是：單一矩陣（不加括號）是完全括號化，兩個矩陣（單一矩陣）加上外括號也是完全括號化的，完全括號化的乘積鏈可以當作單一矩陣處理。
下面上一道課後的證明題：
對n個元素的表達式進行完全括號化時，恰好需要n-1對括號。
證明：
注：采用數學歸納法
已知僅有一個元素時，不需要括號，即0對括號。
假設k個元素時，需要k-1對括號；
當有k+1個元素時，我們可以看作k個元素的完全括號化的乘積鏈外加1個新加的元素。已知我們可以把完全括號化的乘積鏈看作單一矩陣，那麼現有兩個單一矩陣，那麼需再加1對括號，才能再次完全括號化，而由假設知，k個元素的完全括號化需k-1對括號，那麼k+1個元素的完全括號化方案就需要k-1+1對括號；
命題得證！
額，又科普了部分知識，只不過這些科普對後續理解問題都是有用的。
應用動態規劃的方法的步驟：（出自書本）
1、刻畫一個最優解的結構特征
2、遞歸地定義最優解的值
3、計算最優解的值，通常采用自底向上的方法
4、利用計算出的信息構造一個最優解的值
第一步：刻畫一個最優解的結構特征
對於最開始提出的問題，我們看作為矩陣鏈乘設計最優的括號化方案。而設置括號的最終目的就是為了打亂計算順序，通過結合律來找到最小計算代價，就比如下面一個問題33*4*25，是個正常人就會先計算後面兩項，因為這樣好計算，同樣計算矩陣，我們也希望計算的少，計算的快啊，設置括號就變的尤為重要了。
對於完全括號化，每一個括號的作用是將一個鏈乘轉化成兩個完全括號化的鏈乘的積，前面有提到。
因此我最優解的結構特征就如下了：
對於第m個矩陣到第n個矩陣，他的最優解存在於對它的一次劃分中，它的劃分有n-m種情況，我們對這些情況中代價取最小，不就獲得了最優解
而對於每種情況，我們需要劃分後的兩部分矩陣鏈都是最優解，乘積後才可能最小啊，（這部分大家可以用“剪切--粘貼”去反證），這樣問題就轉換成了兩個子部分矩陣鏈的最優括號化方案的問題，以此不斷的遞歸下去。
第二步：遞歸地定義最優解的值
我們的劃分點k可從m到n-1，代價如下所示，每次的代價如下，而最優解只有一個，即它們的最小值：
其一般化的公式如下：
從這裡可以看出，這是一個遞歸的問題，看著很類似上篇所述的鋼條切割問題啊，仔細比對比對吧。
若采用遞歸策略，可能會有很多的重復子問題，無疑提高了計算的復雜度。也可以采取帶備忘的遞歸來降低復雜度。
第三步：計算最優解的值，通常采用自底向上的方法
另外從公式中可以看出，上述計算結果要依賴於m,n（m<n）的所有可能組合。區間[m，n]組合要依賴於它們之間的子區間組合。所以我們采取自下而上的策略，逐漸擴大m,n之間的區間長度，最終算到m=0,n=n，從而獲得最優的括號化方案，
具體方法為：matrix_chain_mutiply.cpp中的void matrix_divide_option(int *num,int** cost,int** point,int length)方法。
第四步、利用計算出的信息構造一個最優解的值
具體解析見matrix_chain_mutiply.cpp最後兩個方法
代碼如下：
matrix.h文件：
#include<iostream>
#ifndef MATRIX_H
#define MATRIX_H
/*
矩陣類
row為其行數
col為該矩陣的列數，
value表示一個二維數組，主要存儲該矩陣各點的值
*/
class matrix
{
public:
matrix(); //默認的構造函數
matrix(int row,int col); //給定行數和列數，構造一個矩陣
virtual ~matrix(); //析構函數
matrix(const matrix& other); //拷貝構造函數
matrix operator*(const matrix& a); //矩陣的乘法
matrix& operator=(const matrix&); //重寫賦值函數
matrix init(); //初始化矩陣
friend std::ostream& operator << (std::ostream&,const matrix &); //重寫輸出
protected:
private:
double **value; //主要用於存儲矩陣各點的值
int col; //列數
int row; //行數
};
#endif // MATRIX_H
matrix.cpp
#include<iostream>
#include "matrix.h"
#include<cstdlib>
#include<ctime>
matrix::matrix() //默認構造函數
{
col = row = 0;
value = nullptr;
}
matrix::matrix(int row, int col) //根據給定行，列數來初始化一個矩陣，並分配相應的內存
{
this->row = row;
this->col = col;
value = new double*[row];
for(int i=0;i<row;i++)
{
value[i] = new double[col];
}
}
matrix::matrix(const matrix& other) //復制構造函數，注意此處要用matrix&，重寫復制構造函數為了防止值復制造成
{
row = other.row;
col = other.col;
value = new double*[row]; //此處使用new分配內存
for(int i=0;i<row;i++)
{
value[i] = new double[col];
}
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
value[i][j]=(other.value)[i][j];
}
}
}
matrix::~matrix()
{
for(int i=0;i<row;i++) //因為構造函數中new分配有內存，所以在析構函數中要對內存進行釋放。
{
delete[] value[i];
}
delete[] value;
}
matrix& matrix::operator=(const matrix& other) //重寫了賦值函數
{
if(this == &other) //防止a=a的情況出現
{
return *this;
}
for(int i=0;i<row;i++) //先釋放原有區域的內存，從此處我們可以上面的判斷的重要性
{ //若沒有上述判斷，a=a在賦值的同時，也將內存釋放了，造成數據丟失
delete[] value[i];
}
delete[] value;
row = other.row; //將成員變量進行復制
col = other.col;
value = new double*[row]; //重新分配內存
for(int i=0;i<row;i++)
{
value[i] = new double[col];
}
for(int i=0;i<row;i++) //對二維數組進行復制
{
for(int j=0;j<col;j++)
{
value[i][j]=(other.value)[i][j];
}
}
return *this;
}
matrix matrix::operator*(const matrix& n) //矩陣的乘法
{
matrix result(row,n.col);
for(int i=0;i<row;i++)
{
for(int j=0;j<n.col;j++)
{
(result.value)[i][j] = 0;
for(int k=0;k<n.row;k++)
{
(result.value)[i][j] += value[i][k]*(n.value)[k][j];
}
}
}
return result;
}
matrix matrix::init() //初始化矩陣
{
matrix result(row,col);
srand((unsigned)time(NULL));
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
(result.value)[i][j] = rand()%100;
}
}
return result;
}
std::ostream& operator <<(std::ostream& os,const matrix& m)//將矩陣輸出
{
for(int i=0;i<m.row;i++)
{
for(int j=0;j<m.col;j++)
{
os << (m.value)[i][j] << '\t';
}
os << std::endl;
}
return os;
}
matrix_chain_mutiply.cpp(核心)
#include<iostream>
#include "matrix.h"
const int SIZE = 5; //SIZE的大小決定了矩陣的數量（SIZE-1），可自行改變
const int max_size = 2147483647;
void matrix_divide_option(int *,int **,int **,int); //確定最優的括號化方案
void show(int **); //輸出二維數組
void print(int**,int,int); //輸出矩陣鏈乘的括號化方案
matrix matrix_mutiply(int**,int,int,matrix*); //獲得矩陣鏈乘的最終結果矩陣
int main()
{
using namespace std;
cout << "input " << SIZE << " number(press enter to end your input)：" << endl;
int *num = new int[SIZE]; //用於存儲矩陣A[i]下標為num[i]*num[i+1];
int i=0;
cin >> num[i]; //獲得矩陣的行列數
while(cin.get() != '\n')
{
i++;
cin >> num[i]; //讀取數組維數；
}
cout << endl << "what you input is:" << endl;
for(int j=0;j<SIZE;j++)
{
cout << num[j] << "-----"; //展示輸入的是否正確
}
cout << endl << endl;
matrix* test = new matrix[SIZE-1]; //為矩陣數組分配內存
for(int j=1;j<SIZE;j++)
{
matrix m(num[j-1],num[j]); //初始化矩陣大小
test[j-1] = m.init(); //初始化該矩陣各點的值
}
cout << "矩陣信息如下：" << endl;
for(int j=0;j<SIZE-1;j++)
{
cout << test[j] << endl; //輸出矩陣信息
}
int **cost = new int*[SIZE-1]; //存儲矩陣相乘時，各標量乘法次數，即代價表
int **point = new int*[SIZE-1]; //存儲矩陣括號化方案時的分割點
for(int j=0;j<SIZE-1;j++)
{
cost[j] = new int[SIZE-1]; //分配內存
point[j] = new int[SIZE-1];
}
matrix_divide_option(num,cost,point,SIZE-1); //獲取劃分方案，獲得最小的代價
cout << "各區間的計算代價：" << endl;
show(cost);
cout << endl;
cout << "區間劃分點所在的位置：" << endl;
show(point);
cout << endl;
cout << "輸出完全括號化方案：" << endl;
print(point,0,SIZE-2);
cout << endl << endl;
cout << "輸出結果矩陣：" << endl;
matrix result = matrix_mutiply(point,0,SIZE-2,test);
cout << result;
for(int j=0;j<SIZE-1;j++)
{
delete[] cost[j];
delete[] point[j];
}
delete[] cost;
delete[] point;
delete[] test;
delete[] num;
return 0;
}
/*
此方法主要獲得計算代價，以及括號化方案的劃分點
為此問題解決的核心方法。
num存儲的矩陣的下標，num[i-1]為第i個矩陣的行數，num[i]表示第i個矩陣的列數
因為數組存儲時，最初始的下標為0，所以下述的定義就變的有點不好理解！仔細想想也容易明白。
cost----二維數組，cost[i][j]代表的就是第（i+1）個矩陣到第（j+1）個矩陣的鏈乘的最小計算代價
point----二維數組，point[i][j]代表的就是第（i+1）個矩陣到第（j+1）個矩陣的鏈乘的最佳劃分處，假如為k，則k就是第k+1個矩陣，
（i+1）到(k+1)矩陣屬於左邊的完全括號化矩陣，其余為右側完全括號化矩陣
length代表的是矩陣的個數，即num的長度-1
*/
void matrix_divide_option(int *num,int** cost,int** point,int length)
{
//首先將代價表中的值重置
//下標i到下標j之間的矩陣鏈乘的最小值
for(int i=0;i<length;i++)
{
for(int j=0;j<length;j++)
{
if(i>=j)
{
cost[i][j] = 0; //單個矩陣不存在乘積，代價0，同時也將不合理的下標組合置為0
}
else
{
cost[i][j] = max_size; //先將各合理的組合代價設為最大，以便後續比較使用。
}
point[i][j] = -1; //將所有組合的劃分點置為-1，以便後續記錄。
}
}
/*
l代表矩陣鏈中矩陣的個數，我們這裡從2個矩陣起步.由公式可知，我們要算遍所有的合理組合，同時大區間的組合
還要依賴於其子區間的合理組合，因為完全括號化的性質，最終都歸根於2個矩陣的乘積，所以我們從2個矩陣起步，
逐步向上計算，最終就能計算（0，n）的組合的最優括號化的代價。
*/
for(int l=2;l<=length;l++)
{
for(int i=0;i<=length-l;i++) //此處要注意的i+l-1不能超過數組的個數
{
int j = i+l-1; //矩陣個數要為l，則j-i需滿足j-i+1=l，所以有該等式
int q = 0;
for(int k=i;k<j;k++) //注意k要在區間內移動，利用下述if條件，獲得所有可能值中的最小值，
{
q = cost[i][k] + cost[k+1][j] + num[i]*num[k+1]*num[j+1];
if(q < cost[i][j])
{
cost[i][j] = q;
point[i][j] = k;
}
}
}
}
}
void show(int **p)
{
using namespace std;
for(int i=0;i<SIZE-1;i++)
{
for(int j=0;j<SIZE-1;j++)
{
cout << p[i][j] << '\t';
}
cout << endl;
}
}
void print(int** point,int i,int j)
{
if(i == j)
{
std::cout << "A" << i+1;
}
else
{
std::cout << "(";
print(point,i,point[i][j]); //輸出劃分點左側的完全括號化表達式
print(point,point[i][j]+1,j); //輸出劃分點右側的完全括號化表達式
std::cout << ")";
}
}
/*矩陣鏈乘的方法與括號化方案表達式輸出的方法是同樣的道理*/
matrix matrix_mutiply(int** point,int i,int j,matrix* m)
{
if(i==j)
return m[i];
else
{
matrix m1 = matrix_mutiply(point,i,point[i][j],m);
matrix m2 = matrix_mutiply(point,point[i][j]+1,j,m);
return m1*m2;
}
}
該問題的解決代碼在上述三個文件中。
同時上述代碼也存在一定的問題，關於內存是否洩漏以及代碼是否符合規范，本人不是非常熟悉。望各位大神，看後覺得有什麼問題，直接回復，我也希望提高，畢竟code能力有待提高。
以上問題也屬於典型的動態規劃問題，也屬於遞歸向迭代的轉換。
總結：
應用動態規劃的方法的步驟：
1、刻畫一個最優解的結構特征
2、遞歸地定義最優解的值
3、計算最優解的值，通常采用自底向上的方法
4、利用計算出的信息構造一個最優解的值
可憐，100分還沒人理你，給我吧。
動態規劃問題可以有tD/eD的形式，n^t為問題的大小，n^e為問題所依賴的子問題的大小
1D/1D型，最長上升子序列
2D/0D型，最長公共子序列
2D/1D型，多源最短路徑
2D/2D型，雙背包問題
當然可以有3D/1D或者更高的。
動態規劃題目千變萬化，主要是要學會思考方法，要能看到題目很快找出題目中的狀態，找准狀態後就基本沒有難度了
#include <stdio.h>
#include <limits.h>
#include<stdlib.h>
#define LENGTH 6
void MatrixChainOrder(int p[],int m[][LENGTH],int s[][LENGTH])
{
int n=LENGTH;
int i,j,k,r,t;
for(i=0;i<n;i++)
m[i][i]=0;
for( r=1;r<n;r++)
{
for(i=0;i<n-r;i++)
{
j=i+r;
m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];
s[i][j]=i;
for(k=i+1;k<j;k++)
{
t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
printf("t=%d;,m[%d][%d]=%d\n",t,i,j,m[i][j]);
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
int main()
{
int p[] = {30,35,15,5,10,20,25};
int m[LENGTH][LENGTH];
int s[LENGTH][LENGTH];
int i,j,k;
MatrixChainOrder(p,m,s);
printf("最少數乘次數：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%8d",m[i][k]);
printf("\n");
}
printf("斷開位置：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%4d",s[i][k]);
printf("\n");
......余下全文>>
