文档介绍：计算机算法设计 与分析
第三章动态规划
引言
分治法求解问题的关键是原问题可分解,而且分解得到的子问题相互对立且可解。
动态规划算法与分治法很类似,其基本思想也是将待求解问题分解成若干子问题,现求解子问题然后再将结果合并。
它们之间有什么不同呢?
引言
不同:
适合用动态规划算法解决的问题经过分解得到的子问题往往并不独立。如果用分治法来解决可能因为分解的子问题数目过多而使算法没有实际意义。
引言
动态规划是如何克服的呢?
有些操作在子问题间要被执行好多次,为了避免大量的重复操作,动态规划技术利用一个表来记录这些操作的结果,从而保证时间复杂性为多项式时间。
动态规划算法适用于解决最优问题。
引言
通常按照下面4步设计:
找出最优解的性质,并刻画其结构特征;
递归地定义最优值;
以自底向上的方法计算出最优值;
根据计算最优值时得到的信息,构造最优解。
注:1-3动态规划的基本步骤,如果只需要最优值,步骤4可以不要。如果需要最优解,则需要执行4。
矩阵连乘问题
练****有三个矩阵:
A1为10*100,A2为100*5,A3为5*50
求A1 * A2 * A3 需要执行基本乘法的最小值。
如果矩阵A是一个p*q的矩阵,B是q*r的矩阵,则乘积C=AB是一个p*r的矩阵。在上述算法中,基本操作的时间复杂性为p*q*r。
void matrixmultiply(int **a,int **b,int **c,int ra, int ca,int rb,int cb)
{
if(ca!=rb) error(“矩阵不可乘”);
for(int i=0;i<ra;i++)
for(int j=0;j<cb;j++) {
int sum=a[i][0]*b[0][j];
for(int k=1;k<ca;k++)
sum+=a[i][k]*b[k][j];
c[i][j]=sum;}
}
矩阵连乘问题
给定n个矩阵,其中Ai与Ai+1是可乘的,i=1,2,…,n-1。我们来研究这n个矩阵连乘积。
矩阵连乘问题
矩阵具有结合律,所以矩阵连乘积可以有许多不同的计算次序。矩阵的次序可以用括号来确定。如果说一个矩阵连乘积的计算次序完全确定,也就说该连乘积已完全加括号,则可以反复调用2个矩阵相乘的标准算法来计算出矩阵连乘积。
矩阵连乘问题
完全加括号: