动态规划（一）
动态规划基本步骤
- 找出最优解的性质，并刻划其结构特征。
- 递归地定义最优值。
- 以自底向上的方式计算出最优值。
- 根据计算最优值时得到的信息，构造最优解。
动态规划算法基本要素
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题：递归算法求解问题时，每次产生的子并不总是新有些子问题被反复计算多次。
矩阵连乘问题
给定 n个矩阵｛ A1,A 2,…,A ,…,A n｝，其中 Ai 与Ai+1Ai+1 Ai+1是可乘的， i=1 ,2… ，n-1。如何确定计算矩阵连乘积的次序，使得依此序计算矩阵连乘积需要的数乘次数最少。
问题理解：
给定n个矩阵{A1,A2,…,An,}， 其中Ai与Ai+1是可乘的，i=1,2,…,n-1 。考察这n个矩阵的连乘积A1A2…An
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积
最优解结构特征：
特征：计算 A[i:j] A[i:j] 的最优次序所包含计算矩阵子 的最优次序所包含计算矩阵子 链 A[i:k] A[i:k] 和A[k+1:j] A[k+1:j] 的次序也是最优的。
递归地定义最优值：
计算量（最优值）：A[i:k]的计算量加上A[k+1:j]的计算量，再加上 A[i:k]和A[k+1:j]相乘的计算量。
建立递归关系：
设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则 原问题的最优值为m[1,n]；
当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n;
当i<j时，m[i,j]=m[i,k]+m[k+1,j]+pi-1pkpj ; 这里Ai 的维数为pi-1 pi ;pi-1pkpj是因为最后结果为维度为pi-1 pj即pi-1 pj个元素，每个元素要乘pk次。(pk为k+1的行数)
可以递归地定义m[i,j]为：
m[i,j]=0（i=j）；min{ m[i,k]+m[k+1,j]+pi-1pkpj }(i<j)
计算最优值：
构造最优解：
void MatrixChain(int *p,int n,int **m,int **s)
{//p[i]记录Ai-1的行数，为p[j]记录Aj的列数，n为矩阵个数，m为最优值，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++){
int j=i+r-1;//j为n
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++){
int t=m[i][k]+m[k+1][j]+p[i-1]p[k+1]p[j];
if(t<m[i][j]){
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
代码实现：
复杂度分析：
算法matrixChain的主要计算量取决于算法中对r， i和k的3重循环。循环体内的计算量为O(1)，而3重 循环的总次数为O(n3)。因此算法的计算时间上界 为O(n3)。算法所占用的空间显然为O(n2)。
