数据结构与算法 数塔问题.doc

数塔问题 有形如图1.3-8所示的数塔从顶部出发在每一结点可以选择向左走或是向右走一起走到底层要求找出一条路径使路径上的值最大 ? ? ? 图1.3-8 这道题如果用枚举法在数塔层数稍大的情况下如40则需要列举出的路径条数将是一个非常庞大的数目 如果用贪心法又往往得不到最优解 在用动态规划考虑数塔问题时可以自顶向下的分析自底向上的计算从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是