题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。

输入描述
输入的第一行包含一个整数 N（1\le N\le 100），表示三角形的行数。
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。

输出描述
输出一个整数，表示答案。

输入输出样例
示例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
30

运行限制
最大运行时间：1s
最大运行内存: 128M

题目简要:

这道题要我们求这个数字三角形中自上到下和最大的路程中的和，也就是要求和最大的通路

解题思路

这道题乍一看使用贪心算法，但是实际上并不是，贪心是一条路走到黑，贪心会一直选最大的那个数并且相加，那么有没有想过一个问题，如果说你选的这个是最大的，那如果后面都是小数，那就得不偿失了，就比如以下两个路径:

3->7->1->2->1 和3->1->6->9->8

如果我用贪心的思维，直接选了3->7这条路的话，那么后面的数会很小，加起来的总和远远小于第二条一开始选小的路，所以说贪心是失效的，那得用什么算法?

首先分析一下题目，题目说数据一共最大有100行，而且行数在一开始是已知为n的，那么

金字塔最底下的数是唯一确定为n的，每个路径都要经过最后一行的元素，所以说我们可以定义一个数组dp，dp元素的数量是n，假设这个数组存放的是 每一个路径到达最后一行的最优和时，我们就可以遍历整个数组，拿到每一路径最优和的最大值，就完成题目了。

什么时候才是最优呢

我们一步一步来，假设金字塔只有两行，如图所示

这时候，到达最低点只有两个路径，7->3,7->8，他们的和分别为10，15,让对应的dp[0]和dp[1]赋值

此时金字塔又增加一行，如图所示:

这时候3可以与8配对也可以与1配对，8可以与1配对也可以与0配对，配对之后就达到了最低点，这时候到达同一点1就会出现两条路径,分别是：

7->3->1 和为11               …舍去

7->8->1 和为16              …

要想使最后的和最大，毫无疑问我们选第二条，那么第一条就相应地舍去了，然后对应的dp[0],dp[1],dp[2]赋值

再把金字塔增加一行，如图所示:

此时8可以与2配对，又可以与7配对，1可以与7和4配对，0可以与4和4配对，因为我们上面已经判断了到达8，1，0各自最大的那条路径的和，所以我们只需要最大路径的和加上每一个路径的数即可，就有下面几条路径：
S8 ->2 =20

S8 ->7 =27

S1->7 = 23…舍去

S1->4 = 20

S0->4 = 19…舍去

S0->4 = 19

其中S8代表的是到达8时候的最大路径和

我们就又得到到最低点时候的最大路径，再把相应的dp[0],dp[1],dp[2],dp[3]赋值

一直循环往复下去，不难发现，我们需要保留上一次的dp值才能算出下一步的dp值，而且到达最低点的每个元素的dp值我们并不会删去，这就是动态规划的思想，上一步保留留作下一步判断的关键。

同时我们也发现，金字塔边长的元素到达最底部的时候，路径是唯一的，第0位数字从第一行一直加第0位数字直到最后一行，最右边的元素也是，从第0位一直 加到第n位，这两个数是不需要额外判断最优的，而其他需要我们判断到达此处是否最优

下面是代码展示

<code>#include <stdio.h>
int dp[100] = {0};
int temp[100]={0};//临时放数的数组
int old_dp[100] = {0};//放置前一行dp

int main(void)
{
	int n,x,y,z,i;
	scanf("%d",&n);
	for(x=0;x<n;x++)//一行判断一次
	{
		for(y=0;y<=x;y++)
		{
			scanf("%d",&temp[y]);
		}
		for(i = 0;i<100;i++)
		{
			old_dp[i] = dp[i];//先把上一个dp给备份了，避免了前一个dp已经变化成X行的dp了，
			//而后面使用X-1行dp的时候却调用了X行dp的情况
		}
		for(z=0;z<=x;z++)
		{
			int left,right;//一个左元素，右元素
			if(z==0 || z==x)//金字塔边长元素不需要判断
			{
				if(z==0) dp[z] = old_dp[z] + temp[z];
				else dp[z] = old_dp[z-1] + temp[z];
			}
			else
			{
				left = old_dp[z-1]+temp[z];//上一行左元素加到z点
				right = old_dp[z] + temp[z];//上一行右元素加到z点
				dp[z] = (left>right)?left:right;//判断两个路径哪个最优
			}
		}
	}
	int max,s;
	max = dp[0];
	for(s=0;s<n;s++)
	{
		max = (max>dp[s])?max:dp[s];
	}
	printf("%d",max);
	return 0;
}</code>