数字三角形问题

数字三角形问题

时间： 1ms        内存：64M

描述：

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

输入：

输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

输出：

输出数据只有一个整数，表示计算出的最大值。

示例输入：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

示例输出：

30

提示：

参考答案（内存最优[792]）：

#include <stdio.h>
#include <string.h>
#define N 110
int dp[N][N];
int maxx(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<=i;j++)
            scanf("%d",&dp[i][j]);
    for(i=n-2;i>=0;i--)
        for(j=0;j<=i;j++)
            dp[i][j]+=maxx(dp[i+1][j],dp[i+1][j+1]);
    printf("%d\n",dp[0][0]);
    return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>   
 #include <memory.h>   
 #define MAX_NUM 100   
 int D[MAX_NUM + 10][MAX_NUM + 10];   
 int N;   
 int aMaxSum[MAX_NUM + 10][MAX_NUM + 10];   
 main()   
 {   
int i, j;   
scanf("%d", & N);   
 for( i = 1; i <= N; i ++ )   
 for( j = 1; j <= i; j ++ )   
 scanf("%d", &D[i][j]);   
 for( j = 1; j<= N; j ++ )   
 aMaxSum[N][j] = D[N][j];   
 for( i = N ; i > 1 ; i -- )   
 for( j = 1; j < i ; j ++ ) {   
 if( aMaxSum[i][j] > aMaxSum[i][j+1] )   
 aMaxSum[i-1][j] = aMaxSum[i][j] + D[i-1][j];   
 else   
 aMaxSum[i-1][j] = aMaxSum[i][j+1] + D[i-1][j];   
 }   
 printf("%d", aMaxSum[1][1]);   
 }   

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。