数字三角形问题

系统管理员 2022-05-16 01:24 208阅读 0赞

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

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。  
Input  
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。  
Output  
输出数据只有一个整数，表示计算出的最大值。  
Sample Input  
5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5  
Sample Output  
30

这#include <stdio.h>
    #include <stdlib.h>
    int main()
    {
        int n,i,j;
        int a[101][101],b[101][101];\
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=1;i<=n;i++)
        {
            b[n][i]=a[n][i];
        }
        for(i=n-1;i>=1;i--)
        {
            for(j=1;j<=i;j++)
            {
                if(b[i+1][j]>b[i+1][j+1])
                {
                    b[i][j]=b[i+1][j]+a[i][j];
                }
                else
                {
                    b[i][j]=b[i+1][j+1]+a[i][j];
                }
            }
        }
        printf("%d\n",b[1][1]);
        return 0;
    }
    里写代码片

动态规划：树塔问题：动态规划特点;用数组保存原来数据，再用一个数组保存所要的数据，找到一个起始点，套用递归公式，进行一次遍历存储。最后直接提取值。  
本题结题思路：先用一个数组存储原来数据，将基层数据复制给数组（递归起点），用递归公式进行结题。此题找最大路径，所以上面的一个值等于，（下面一个值和右下值比较大小，大的值加上原来a中数据 等于b的数值。

发表评论取消回复

表情：

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

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

相关阅读

相关数字三角形

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

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

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关 1730 数字三角形问题

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

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