算法分析讲课大纲动态规划之求矩阵连乘积问题（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）第一小节动态规划问题——最短路径问题一在正式提出动态规划法前我们先看一个数学例子：例1：在x+x2+x3+…+xn=a是约束条件下，求的极大值.令(0)令且可得ax=x,所以x=a/2故同理令所以ax=2x,x=a/3所以f3(a)=用数学归纳法可以证明：fn(a)=,x1=x2=x3=…=xn=证明：1：n=1…2：设fn(a)=,x1=x2=x3=…=xn=成立，则fn+1(a)=max(+fn(a-x))=max()令y=y’==所以nx=a-x,(n+1)x=ax=fn+1(a)=+n=我们刚才的解题策略是：“摸着石头过河”，f2利用f1的结果，f3又利用f2的结果。。。。。。类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。。。。。最后取得胜利。。。在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（RichardBellman）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法——动态规划。分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据中找出最大者为例，说明分治法的“静”和动态规划法的“动”的区别。下面我们以具体的例子来说明如何运用动态规划算法来求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。对教材68页上的里子给予简要说明（因为书上的文字叙述有些含混晦涩，对符号的说明不清晰）y1OAF2K3P1S2U下面精讲一个例子21223C2G3L4Q5T34123DHMR22134323介绍这个图的特点…..从而说明从O到A的最短路径必由7段而不是更多或更少段组成。其行进路线必然是x和y单调递增的（非严格单调）。从O(0,0)到U（4，3）点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C=35.如果采用穷举法进行搜索，需要进行35*6=210次加法，34次比较。下面我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do，以A为起点到U的最短距离为DA---,用dij表示（i,j）边的长度。显然Ds=dsu=2,Dt=dTU=3,DQ=min{2+2,5+3}=4DP=1+Ds=1+2=3DR=3+DT=3+3=6DL=min{Dlq+DQ,dLP+DP}=min{4+DQ,2+Dp}=min{4+4,2+3}=5Dk=3+Dp=3+3=6DM=min{2+DQ,4+DR}=min{2+4,4+6}=6DN=4+DR=4+6=10DF=2+DK=2+6=8DG=min{1+DK,3+DL}=min{1+6,3+5}=7DH=min{1+5,1+6}=6DJ=min{3+DM,3+DN}=min{3+6,3+10}=9DC=min{2+DF,2+DG}=min{2+8,2+7}=9DD=min{4+DG,2+DH}=min{4+7,2+6}=8DE=min{1+DH,2+DJ}=min{1+6,2+9}=7DA=min{3+DC,2+DD}=min{3+9,2+8}=10DB=min{2+DD,3+DE}==min{2+8,3+7}=10Do==min{1+DB,2+DA}=min{1+10,2+10}=11共进行了29次加法，12次比较。由Do=1+DB=11回溯，可得到最短路径为O—>B-D->HL—>P-S-UO-B-E-H-L-P-S-U推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+（m+n-2）次加法，mm次比较；而如果用穷举法，需要次加法，次比较。若m=n,动态规划法要做2n2+2n-2次加法，n2次比较，因此复杂度为O(n2);而穷举法需要次加法，次比较，>O(n2n+1)。第二小节动态规划问题——货郎担问题动态规划方法的思想---动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优