图一表示一个5行的数字三角形假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大 每一步只能由当前位置向下或向右下。

你嘚程序要能接受标准第一出厂价只能输入3个整数第一行包含一个整数T，表示总的测试次数
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。

输出每次测试的最大值并且占一行

这是一道难度二级的动态规划经典例题，在看到数字三角形的构造时我们首先想到用二维数组来存放整个三角形（行与列），所求是路径最大数字和也许有人会想到贪心算法来实现，但是贪心算法在这里是不适用嘚因为凡事不能只看现在嘛，贪心中一次查找到大值最后总值却不是，所以眼光放长我们要的是最后的最大，来尝试用动态规划解決问题吧用动态规划也有不同的思路和方法，首先我们的切入点是由下至上的回溯依层次更换改动大值，回到顶端时就是结果咯。

手记草稿小流程（丑，但能看_——）

1.数学思想发现规律

2.递推思想，操作效率

过程比较复杂容易漏缺。

注意仳较大小时&&的是使用以及C++中《》的使用。