算法设计与分析提纲提纲在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。动态规划Vs.贪心策略动态规划Vs.分治策略比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。动态规划算法的的基本思想动态规划算法的一般步骤提纲知识点矩阵连乘问题矩阵连乘问题两个矩阵的相乘问题三个矩阵的相乘问题考察{A1,A2,A3}三个矩阵连乘不同计算次序下的计算量矩阵连乘积的最优计算次序问题方案1：穷举搜索法用动态规划法求解求解步骤分析最优解的结构求解步骤建立递归关系当i=j时当i<j时求解步骤计算最优值PublicstaticvoidmatrixChain(int[]p,int[][]m,int[][]s){intn=p.length-1;for(inti=1;i<=n;i++)m[i][j]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=I;for(intk=i+1;k<j;k++){intt=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;}}}}举例说明123456算法复杂性分析求解步骤构造最优解举例动态规划算法的基本要素*多阶段决策过程动态规划算法求解思路动态规划算法的基本要素最优子结构子问题重叠性质备忘录方法备忘录方法的求解过程备忘录方法的复杂性分析两种方法应用方面的考虑提纲最长公共子序列凸多边形最优剖分多边形游戏图象压缩电路布线流水作业调度0-1背包问题凸多边形最优三角剖分凸多边形的性质v1凸多边形最优三角剖分问题一个有趣的发现表达式语法树v1凸n边形的三角剖分v1求解凸多边形最优三角剖分问题最优子结构性质求解凸多边形最优三角剖分问题最优三角剖分的递归结构求解凸多边形最优三角剖分问题计算最优值求解凸多边形最优三角剖分问题构造最优解多边形游戏多边形游戏333解题思路最优子结构分析最优子结构分析满足最优子结构性质解题思路递归求解递归求解递归求解递归求解解题思路计算最优值最长公共子序列什么是子序列？什么是公共子序列？最长公共子序列问题解题思路最长子序列的最优子结构性质解题思路子问题的递归结构分析建立子问题最优值的递归关系解题思路计算最优值publicstaticintlcsLength(char[]x,char[]y,int[][]b){……//初始化，如果i=0或j=0，则c[i][j]=0；for(inti=1;i<=m;i++)for(intj=1;j<=n;j++){if(x[i]=y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]=){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}returnc[m][n];}解题思路构造最长公共子序列电路布线1最优子结构性质最优子结构性质电路布线问题满足最优子结构性质递归计算最优值构造最优解图象压缩图象压缩图象的变位压缩存储方式图象的变位压缩存储方式图象压缩问题最优子结构性质递归计算最优值publicstaticvoidcompress(intp[],ints[],intl[],intb[]){……//初始化，n=总像素数，s[0]=0；for(inti=1;i<=n;i++){b[i]=length(p[i]);intbmax=b[i];s[i]=s[i-1]+bmax;l[i]=1;for(intj=2;j<=i&&j<=lmax;j++){//lmax=256if(bmax<b[i-j+1])bmax=b[i-j+1];if(s[i]<s[i-j]+j*bmax){s[i]=s[i-j]+j*bmax;l[i]=j;}}s[i]+=header;//header=11}}构造最优解流水作业调度流水作业调度最优子结构性质递归计算最优值流水作业调度的Johnso