动态规划：
- 将大问题划分为具有相同特征的小问题；
- 小问题之间往往相互联系；
- 从小问题一步步求解大问题。
适合求解最优解问题
矩阵连乘问题描述
有n个矩阵连乘，如何找到最小的加括号方式以及最小的次数
疑问
A(35)A(57)A(7*2)的向乘次数和划分有关系吗？
(A(3*5)A(5*7))A(7*2) 相乘次数： (3*5*7)+(3*7)*2 = 147
A(3*5)(A(5*7)A(7*2)) 相乘次数： (5*7*2)+3*(5*2) = 100
答案很明显是有关系的。
分析
求 A1A2A3…An
定义 AiAi+1…Ak…Aj-1Aj 子列， 可看成是Ai…Ak，Ak…Aj
确定k的位置，然后按照递归的思想来逐步解决
求得结果后，使i=1，j=n原问题即可求解。
建立递归关系（状态转移方程）
设
Ai…Aj相乘 的最小数乘次数存储于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个
当i=j时，m[i][j] = 0;
当i<j时，m[i][j] = m[i][k]+m[k+1][j]+Pi-1PkPj
k在i，j之间取值，取值范围为i<=k<j
有递推关系如下：
动态规划的最优子结构性质是：
问题的最优解包含了其子问题的最优解。
最优子结构性质是问题可用动态规划法求解的显著特征。
Ak+1…Aj，Ai…Ak的最优划分也包含在Ai…Aj的最优划分中
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]构造出最优解
代码如下：
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;
}
}
}
}
}
