实验报告2. 动态规划

1、WUHANTEXTILEUNIVERSITY算法设计与分析实验报告实验名称动态规划学院数学与计算机学院班级信科00000学号6666666666姓名0000002016年学号姓名实验日期实验名称动态规划【实验目的】理解动态规划算法的思想，能灵活利用动态规划算法解决实际计算问题。【实验内容】参考源码MatrixChain.cpp,RecurveMatrixChain.cpp,lookupMatrixChain.cpp1阅读参考代码，理解动态规划算法的主要数据结构；2比较动态规划算法和分治算法的异同；3比较规划算法和备注算法的异同；4针对4.6,4.7两节问题，在已有动态规划算法基础上，编程求解最

2、优解；【实验原理】（含相关算法流程图，可写多页）【实验环境】微型计算机；Windows7操作系统；Codeblocks、vs2012集成开发环境。【实验过程与结果】(附主要源码及运行结果截图)最长单调子序列问题#include#defineMAXLENGTH1000usingnamespacestd;intLongestIncreasingSubsequence(intX,intn,intc,intline)intpathMAXLENGTH;for(inti=0;in;+i)pathi=i;c0=1;输入数组for(inti=1;in;+i)ci=1;for(intj=0;j=Xj&cj+1c

3、i)ci=cj+1;pathi=j;intmax=0;intend=-1;得到最大和获得最长递增子序列的最后一个元素的索引intcMAXLENGTH;intlineMAXLENGTH;while(cinn,n!=0)for(inti=0;iXi;intmax=LongestIncreasingSubsequence(X,n,c,line);coutLongestIncreasingSubsequencesLength:max=0;-i)coutlinei;coutendl;intresn+ln+l;memset(arr,-1,sizeof(int);memset(res,-1,sizeof(i

4、nt);for(inti=1;i=n;i+)for(intj=1;jarrij;/初始化res结果数组for(inti=1;i=1;i-)for(intj=1;j=i;j+)/动规填表resij=max(resi+1j,resi+1j+1)+arrij;严/打印res数组for(inti=1;i=n;i+)for(intj=1;j=i;j+)coutresij;coutendl;coutendl;*/coutresllendl;/最大路径和值/找出靠右路径inty=1;coutarr1y;顶部最大for(inti=2;i=n;i+)/从上往下找，只需要比较y和y+1,相应输出“最大值下标对应的

5、”原值if(resiy=resiy+l)coutarriy+1:y=y+l;更新yelse厂吨;coutendl;return0;DiWpiirQliMMglNiPebiWvHE645方箱essreti.imMlQ(QiO)exiBBJLtinntijw:89.457ste-F?snvkeyto-critLrv.H-懊洎新音输人古i:2I41&-4S-fik.中药诃述【实验小结】分治法与动态规划主要共同点：一者都要求原问题具有最优子结构性质，都是将原问题分而治之,分解成若干个规模较小（小到很容易解决的程序）的子问题然后将子问题的解合并，形成原问题的解.分治法与动态规划实现方法：分治法通常利用递归求解.动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解.分治法与动态规划主要区别：分治法将分解后的子问题看成相互独立的.动态规划将分解后的子问题理解为相互间有联系，有重叠部分.2.相同点解决的问题都需要最优子结构备忘录方法与动态规划和递归的区别：1、动态规划是自低向上，备忘录方法是自顶向下，递归是