数字三角形问题

Myth丶恋晨 2022-07-13 01:52 181阅读 0赞

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

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

#### Example Output ####

30

#include<stdio.h>
    int main()
    {
        int n;
        int i,j;
        int a[100][100]={0};
        int d[100][100]={0};
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=0;i<n;i++)
        {
            d[n-1][i]=a[n-1][i];
        }
        for(i=n-1;i>=1;i--)
        {
            for(j=0;j<i;j++)
            {
                if(d[i][j]>d[i][j+1])
                    d[i-1][j]=d[i][j]+a[i-1][j];
                else
                    d[i-1][j]=d[i][j+1]+a[i-1][j];
            }
        }
        printf("%d\n",d[0][0]);
        return 0;
    }

[1730.png]: http://www.sdutacm.org/image/1730.png

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关数字三角形

给定一个由n行数字组成的数字三角形，设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。 ![Image 1][] 参考代码： in

心已赠人/ 2022年08月02日 06:40/ 0 赞/ 168 阅读

相关数字三角形问题

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

Myth丶恋晨/ 2022年07月13日 01:52/ 0 赞/ 182 阅读

相关数字三角形问题

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

Myth丶恋晨/ 2022年07月12日 02:46/ 0 赞/ 186 阅读

相关数字三角形问题

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

悠悠/ 2022年07月12日 02:46/ 0 赞/ 216 阅读

相关动态规划—数字三角形问题

数字三角形问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 给定一个由n行数字组成的数

╰+哭是因爲堅強的太久メ/ 2022年07月11日 01:52/ 0 赞/ 203 阅读

相关数字三角形问题

数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Proble

曾经终败给现在/ 2022年05月30日 10:07/ 0 赞/ 186 阅读

相关数字三角形问题

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

系统管理员/ 2022年05月16日 01:24/ 0 赞/ 211 阅读

相关数字三角形问题

数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定一个由n行数字组成

谁践踏了优雅/ 2022年02月17日 13:00/ 0 赞/ 231 阅读

相关数字三角形问题

数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定一个由n行数字组成

灰太狼/ 2022年02月16日 02:14/ 0 赞/ 247 阅读

相关 1730 数字三角形问题

数字三角形问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定一个由n行数字组成

亦凉/ 2022年02月15日 06:15/ 0 赞/ 219 阅读