一、题意：给定一些数，成三角形排列。从上往下走，每个数只能往它相邻的两个数走，一直走到底端得到一条线路。这条线路上的数的和最大是多少

二、思路：简单的动态规划。dp[i+1][j+1]:=以第i+1行j+1列为最后一个数字所能得到的最大和。所有的初始值均设为0，那么从上往下递推，可得到以每一个数为结尾的最大和，这样只要比较最后一行所能得到的最大和是多少即可。递推式为：dp[i+1][j+1]=max(dp[i][j],dp[i][j+1])+tri[i][j];

三、代码：

#include"iostream"#include"stdio.h"#include"string.h"using namespace std;const int MAXN=355;int dp[MAXN][MAXN];int tri[MAXN][MAXN];int GetMaxSum(int n){    memset(dp,0,sizeof(dp));    for(int i=0;i
      
       res) res=dp[n][j+1];    }    return res;}int main(){    int n;    while(scanf("%d",&n)==1)    {        for(int i=0;i