动态规划算法的应用实验报告

实验二动态规划算法的应用一、实验目的1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。2．熟练掌握分阶段的和递推的最优子结构分析方法。3．学会利用动态规划算法解决实际问题。二、实验内容1.问题描述：题目一：数塔问题给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。输入样例（数塔）：9121510682189519710416输出样例（最大路径和）：59三、算法设计voidmain(){申明一个5*5的二维数组；for(inti=0;i5;i++){for(intj=0;j=i;j++){输入数组元素p[i][j];}}for(intk=0;k5;k++){for(intw=0;w=k;w++){输出数组元素p[k][w];}}for(inta=4;a0;a--){for(ints=0;s=a;s++){if(p[a][s]大于p[a][s+1])p[a-1][s]等于p[a-1][s]加p[a][s];elsep[a-1][s]等于p[a-1][s]加p[a][s+1];}}输出p[0][0]}FTFTintmain()inti=0inta=4i5coutp[0][0]intj=0j=icinp[i][j]i++j++a0a--FTints=0s=aFTs++p[a][s]p[a][s+1]p[a-1][s]=p[a-1][s]+p[a][s];TFp[a-1][s]=p[a-1][s]+p[a][s+1]四.程序调试及运行结果分析五.实验总结虽然这个实验比较简单，但是通过这次实验使我更加了解的动态规划法的好处和、，在解决问题时要尝试使用动态规划，这样就有可能得到一种即简单复杂性有不高的算法。附录：程序清单（程序过长，可附主要部分）#includeiostream.hintmain(){intm,n;intp[5][5];cout输入矩阵的下三角的元素!!endl;for(inti=0;i5;i++){for(intj=0;j=i;j++){cout输入第i+1行j+1列的元素endl;cinp[i][j];}}for(intk=0;k5;k++){for(intw=0;w=k;w++){coutp[k][w];}coutendl;}for(inta=4;a0;a--){for(ints=0;s=a;s++){if(p[a][s]p[a][s+1])p[a-1][s]=p[a-1][s]+p[a][s];elsep[a-1][s]=p[a-1][s]+p[a][s+1];}}cout最大路径和为:p[0][0]endl;return0;}