动态规划—矩阵链相乘.pptVIP

超人的能量项链;例如：项链有四个能量珠，能量数组p 如下：p1=4,p2=5,p3=2,p4=8 则这四颗能量珠头尾部能量分别为 （4，5）、（5，2）、（2，8）、（8，4） ; ;得到项链的最大能量了吗？;7.4矩阵链相乘;两个矩阵相乘;三个矩阵相乘;是否让你吃惊？;完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;矩阵连乘问题;关于计算量;规模为4的情况;A1 5?10 A2 10?4 A3 4?6 A4 6?10 2、计算规模为3的子问题 (1)计算A1A2A3所需乘法次数，有两种结合方法: (A1A2)A3和A1(A2A3),选最好的一种：;A1 5?10 A2 10?4 A3 4?6 A4 6?10 (2)计算A2A3A4所需乘法次数，有两种结合方法:(A2A3)A4和A2(A3A4)，选最好的一种： ;A1 5?10 A2 10?4 A3 4?6 A4 6?10 3 计算规模为4的原问题A1A2A3A4所需乘法次数，有三种结合方法: ( A1A2A3)A4 、 (A1A2)(A3A4) 、 A1(A2A3A4 ) ，选最好的一种： ;用数组元素C[i][j]来存储计算A[i:j]的最少数乘次数;A1 5?10 A2 10?4 A3 4?6 A4 6?10 2、计算规模为3的子问题 计算A[1:3]所需乘法次数，有两种结合方法，选最好的一种： (A[1:2])A3: 计算A[1:2]的计算量+计算（A[1:2]）乘A3的计算量：200+5 ?4 ?6=320 A1(A[2:3]): 计算A[2:3]的计算量+计算A1乘(A[2:3])的计算量：240+5 ?10 ?6=540;A1 5?10 A2 10?4 A3 4?6 A4 6?10 计算A[2:4]所需乘法次数，有两种结合方法，选最好的一种： 840 (A[2:3])A4: 计算A[2:3]的计算量+计算A[2:3]乘A4的计算量：240+10 ?6 ?10=840 A2(A[3:4]): 计算A[3:4]的计算量+计算A2乘(A[3:4])的计算量：240+10 ?4 ?10=640;A1 5?10 A2 10?4 A3 4?6 A4 6?10 3 计算规模为4的原问题A[1:4]所需乘法次数，有三种结合方法，选最好的一种： ( A[1:3])A4: 计算A[1:3]的最小计算量+计算（A[1:3]）乘A4的计算量：320+5 ?6 ?10=620 (A[1:2])(A[3:4]): 200+240+5 ?4 ?10=640 A1(A[2:4] ): 640 +5 ?10 ?10=1140;A1 5?10 A2 10?4 A3 4?6 A4 6?10 ;将例7.1中的中间结果存入数组;特征：计算A[i:j]的最优次序所包含的计算矩??子链 A[i:k-1]和A[k:j]的次序也是最优的。举例 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。;建立递归关系; 的位置只有 种可能;计算最优值;动态规划--自底向上进行计算;课堂练习;C[1:1]=0;C[1:1]=0;C[1:1]=0;C[1:1]=0;用动态规划法求最优解;讨论;程序1：程序没有任何通用性;程序2（先开辟一个较大的存储空间）;程序3：用函数测出字符串的长度;程序4：字符串由用户输入;程序5:动态分配存储空间(推荐）;程序6:双重指针1;int **c;;程序7:双重指针2;int *c[N];与int (*c)[N]的区别