题目描述 Description
如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。
输入描述 Input Description
第一行是数塔层数N(1<=N<=100)。
第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。
输出描述 Output Description
输出最大值。
样例输入 Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
样例输出 Sample Output
86
数据范围及提示 Data Size & Hint
数字三角形
分类标签 Tags 点此展开
解题思路：
这道题是一道很经典的题目了，定义状态为：dp[i][j]表示，从第i行第j个数字到最后一行的某个数字的权值最大的和。那么我们最后只需要输出dp[1][1]就是答案了.
状态转移方程为：dp[i][j] += max( dp[i+1][j+1],dp[i+1][j] );好了， 从第n-1行往上面倒退就好了。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
# include<cstring>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<set>
# include<map>
using namespace std;
# define inf 999999999
# define MAX 123
int a[MAX][MAX];
int main(void)
{
int n;
while ( cin>>n )
{
for ( int i = 1;i <= n;i++ )
{
for ( int j = 1;j <= i;j++ )
{
cin>>a[i][j];
}
}
for ( int i = n-1;i >= 1;i-- )
{
for ( int j = 1;j <= i;j++ )
{
a[i][j] = max(a[i+1][j],a[i+1][j+1])+a[i][j];
}
}
printf("%d\n",a[1][1]);
}
return 0;
}