动态规划算法的应用

数塔问题

给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。

输入样例（数塔）：

9

15

10 6 8

2 18 9 5

19 7 10 4 16

输出样例（最大路径和）：

59

-Application of dynamic programming algorithm for a given number of tower of a few towers, its storage form as shown below the lower triangular matrix. In the few tower, starting from the top in each node can choose to go down or right away, the bottom has been reached. Please find a path, so that path and the largest numerical. Input sample (the number of towers): 915 10 6 82 18 9 519 7 10 4 16 output sample (maximum path and): 59