数字三角形问题

且陶陶

发布于 2023-04-12 14:48:40

3210

文章被收录于专栏：Triciaの小世界Triciaの小世界

数字三角形问题

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

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

Input 输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。
Output 输出数据只有一个整数，表示计算出的最大值。

Sample Input

Sample Output

30

#include <stdio.h>
#include <stdlib.h>

int d[110][110];
int n;
int *maxsum;

int max(int x, int y){
    if(x<y) return y;
    else return x;
}

int main(){
    int i,j;
    scanf("%d",&n);
    for(i = 1;i<=n;i++){
        for(j = 1;j<=i;j++){
            scanf("%d",&d[i][j]);
        }
    }
        maxsum = d[n];
        for(i = n-1;i>=1;--i){
            for(j = 1;j<=i;++j){
                maxsum[j] = max(maxsum[j],maxsum[j+1])+d[i][j];
            }
        }
     printf("%d\n",maxsum[1]);
            return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-11-10，如有侵权请联系 cloudcommunity@tencent.com 删除

output