文件名称：数塔问题的算法c++实现
文件大小：841B
文件格式：CPP
更新时间：2012-07-16 18:09:34
数塔问题 算法实验 动态规划
要找到最大和的前提条件是，要能看到数塔的全貌。在此基础之上，不难发现，该问题应从下而上逐层解决。从倒数第二层开始考虑，对该层的每一个数取其下一层中与其相邻的两个数的较大者。然后把二者相加，结果存储到一个位置。依次倒退到第一层时就可得到最佳结果。 下一个问题是如何解决存储问题，如果把每一次累加的和存储到原表的话，当输出路径时将找不到数塔的原始数据。因此要另辟一个表存储从倒数第二层开始没个数的累加和。为了方便，我们可以开辟一个与原表相同的数组来存储相应位置上的累加和。 还有一个问题是，如何根据累加和与原始数塔数据找到相应的路径。我们来分析一下，对于从倒数第二层开始的每一个数，与其对应的下一个数无非在其左边或右边，只有这两种可能。因此，可以把这两个数区分出左和右，进而，可以用标志量来标识我们取左还是取右。同样，我们再开辟一个与原表相同的数组来存储相应是标识量。我们可以用0表示取左，1表示取右。 最后，总结一下，我们可以把这三张表同时申请出来——用三维数组。