题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大
输入输出格式
输入格式：
第一个行包含 R(1<= R<=1000) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
输出格式：
单独的一行,包含那个可能得到的最大的和。
输入输出样例
输入样例#1：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出样例#1：
30
说明
题目翻译来自NOCOW。
USACO Training Section 1.5
由于此题并不是特别难，所以就不发代码了，但是思路是~~肯定会讲清楚的。
不敢相信，这道题出自IOI1999。但如果我在那个时代，我肯定也做不出来。
蒟蒻一来看到这题，大叫：“哇，这题真简单！贪心就行啦！”
但是贪心法的缺点在此题中一览无余的展现了出来：目光短浅。
如果按照贪心法思路，则：7-8-1-7-5，其和为28；
但是存在着另外一条路：7-3-8-7-5，其和为30。
所以贪心法就OUT了。。。
然后蒟蒻又想：贪心法不行，那搜索总行了吧！
结果这次蒟蒻又想错了……
在本题中，R<=1000，要是用搜索，无论是DFS还是BFS，无论怎样剪枝，只有一种结果：TLE。
所以！！！
本题最简算法就是：递推！
递推共有两种方法可以选择：顺推法和逆推法，两种方法皆可。
顺推法和逆推法实际上很好区别，顺推法是从已知条件出发，向结果推导，而逆推法则是从结果出发，一步一步地往前推导。在本题中，顺推法就是从数塔的上方出发，一直推到最底层。而逆推法就是从最底层出发，往顶层前进。
我是用顺推法的。直接就写了个两重循环。
for(int i=2; i<=n; i++)
for(int j=1; j<=i; j++)
if(b[i-1][j-1]>b[i-1][j]) //因为我们要求最大值，所以要将数塔上一层最大的数加上去。
b[i][j]=b[i][j]+b[i-1][j-1];
else b[i][j]=b[i][j]+b[i-1][j];
上面是主要部分，剩下就是什么输入输出之类的了。