问题描述

　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路

　　径，使该路径所经过的数字的总和最大。

　　●每一步可沿左斜线向下或右斜线向下走；

　　●＜三角形行数≤；

　　●三角形中的数字为整数0，，…；

　　        .

　　（图３.１－１）

输入格式

　　文件中首先读到的是三角形的行数。

　　接下来描述整个三角形

输出格式

　　最大总和（整数）

样例输入

样例输出

 #include <stdio.h>

 #include <string.h>

 #define LEN 100

 #define MAX(X,Y) (X)>(Y)?(X):(Y)

 int main(void)

 {

     int n,i,j,res;

     int dp[LEN+][LEN+];

     memset(dp,,sizeof(dp));

     scanf("%d",&n);

     for (i= ; i<n ; i++)

     {

         for (j= ; j<=i ; j ++)

         {

             scanf("%d",&dp[i][j]);

             if (i>) //每行的数据依次添加上方或左上方中的最大值

             {

                 if (j==)

                     dp[i][j] += dp[i-][j];

                 else

                     dp[i][j] += MAX(dp[i-][j],dp[i-][j-]);

             }

         }

     }

     res = dp[n-][];

     for (i= ; i<n ; i++)//遍历最后一行中的最大值

         if (dp[n-][i] > res)

             res = dp[n-][i];

     printf("%d",res);

     return ;

 }