C语言动态规划&背包数字三角形问题

约定不等于承诺〃 2022-06-01 08:29 212阅读 0赞

### 数字三角形问题 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### 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 ####

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

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2381/pid/1730.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2381/pid/1730.html
[1730.png]: http://acm.sdut.edu.cn/image/1730.png