動態(tài)規(guī)劃：
- 將大問題劃分為具有相同特征的小問題；
- 小問題之間往往相互聯(lián)系；
- 從小問題一步步求解大問題。
適合求解最優(yōu)解問題
矩陣連乘問題描述
有n個矩陣連乘，如何找到最小的加括號方式以及最小的次數(shù)
疑問
A(35)A(57)A(7*2)的向乘次數(shù)和劃分有關(guān)系嗎？
(A(3*5)A(5*7))A(7*2) 相乘次數(shù)： (3*5*7)+(3*7)*2 = 147
A(3*5)(A(5*7)A(7*2)) 相乘次數(shù)： (5*7*2)+3*(5*2) = 100
答案很明顯是有關(guān)系的。
分析
求 A1A2A3…An
定義 AiAi+1…Ak…Aj-1Aj 子列， 可看成是Ai…Ak，Ak…Aj
確定k的位置，然后按照遞歸的思想來逐步解決
求得結(jié)果后，使i=1，j=n原問題即可求解。
建立遞歸關(guān)系（狀態(tài)轉(zhuǎn)移方程）
設(shè)
Ai…Aj相乘 的最小數(shù)乘次數(shù)存儲于m[i][j]中。
S[i][j]存儲最佳斷開位置。
A1：P0*P1
A2：P1*P2
A3：P2*P3
…
Ai：Pi-1*Pi
Ai+1：Pi*Pi+1
…
An：Pn-1*Pn
P0*P1*P2…*Pn——n+1個
當(dāng)i=j時，m[i][j] = 0;
當(dāng)i<j時，m[i][j] = m[i][k]+m[k+1][j]+Pi-1PkPj
k在i，j之間取值，取值范圍為i<=k<j
有遞推關(guān)系如下：
動態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)性質(zhì)是：
問題的最優(yōu)解包含了其子問題的最優(yōu)解。
最優(yōu)子結(jié)構(gòu)性質(zhì)是問題可用動態(tài)規(guī)劃法求解的顯著特征。
Ak+1…Aj，Ai…Ak的最優(yōu)劃分也包含在Ai…Aj的最優(yōu)劃分中
s[i][j]的確定方法：
對于Ai……Aj
k=i, (Ai)(...Aj)
k=i+1, (AiAi+1)(...Aj)
k=j-1, (AiAi+1...Aj-1)Aj
求出m[i][j]的最小k值，存入s[i][j]，
最后遞歸的由s[i][j]構(gòu)造出最優(yōu)解
代碼如下：
void func(int n,int *p,int **m,int **s){
int i,h,j,k,t ;
for(i = 1 ; i <= n ; i++) //i=j，m[i][j]=0
m[i][i] = 0;
for(h = 2 ; h <= n ; h++){ //鏈長h
for(i = 1 ; i < n-h+1 ; i++){
j = i+h-1;
m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(k = i+1 ; k < j ; k++){
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;
}
}
}
}
}
