数字三角形(DP)

约定不等于承诺〃 2022-06-10 05:18 210阅读 0赞

问题：  
　　给定一个由n行数字组成的数字三角形，如下图所示：

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

试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大（每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数）。

输入：  
　　第一行是数字三角形的行数，接下来 n 行是数字三角形中的数字。

比如：

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出：  
　　输出这个最大值。

思路：从最低层向上递推，除最底层外，每一行每个点的最大值等于其本身加上下面一行所对应的左右两点的最大值  
D\[i\]\[j\] = max(D\[i+1\]\[j\],D\[i+1\]\[j+1\]) + D\[i\]\[j\]；

#include <iostream>
    #include <algorithm>
    using namespace std;
    #define MAX 101
    int D[MAX][MAX];
    int n;
    
    
    int MaxSum(int num){
        int i, j;
        for(i = num - 1; i >= 1; i--) //最底层 
            for(j = 1; j <= i; j++) {
                D[i][j] = max(D[i+1][j],D[i+1][j+1]) + D[i][j];
            }
    
        return D[1][1]; 
    } 
    int main(){
        int i,j;
    
        cin >> n;
    
        for(i=1; i<=n; i++) 
            for(j=1; j<=i; j++)
                cin >> D[i][j];
    
        cout << MaxSum(n) << endl;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关数字三角形

数字三角形给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最

ゝ一世哀愁。/ 2024年03月30日 01:33/ 0 赞/ 106 阅读

相关数字三角形

![707e1f04e331a2967263ea5a5377aada.png][] 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面

柔光的暖阳◎/ 2024年03月25日 14:02/ 0 赞/ 115 阅读

相关数字三角形 dp

问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　　径，使该路径所经过的数字的总和最大。　　●每一步可沿左斜线向下或右

短命女/ 2024年02月17日 19:22/ 0 赞/ 63 阅读

相关蓝桥杯算法训练之数字三角形（dp）

算法训练数字三角形时间限制：1.0s 内存限制：256.0MB 问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　　

缺乏、安全感/ 2024年02月17日 19:13/ 0 赞/ 102 阅读

相关数字三角形

题目描述给定一个由n行数字组成的数字三角形，设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大；三角形的第i行有i个数(i=1...n),对于

矫情吗；*/ 2023年10月18日 12:33/ 0 赞/ 79 阅读

相关线性DP AcWing 898. 数字三角形

线性DP AcWing 898. 数字三角形原题链接 [AcWing 898. 数字三角形][AcWing 898.] 算法标签动态规划线性DP

「爱情、让人受尽委屈。」/ 2023年09月28日 12:54/ 0 赞/ 23 阅读

相关 DP 数字三角形(POJ1163)

7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往

朱雀/ 2022年08月18日 02:36/ 0 赞/ 54 阅读

相关数字三角形

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

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

相关数字三角形(DP)

问题：　　给定一个由n行数字组成的数字三角形，如下图所示： 7 　 3 8 　 8 1 0 　

约定不等于承诺〃/ 2022年06月10日 05:18/ 0 赞/ 211 阅读

相关 hiho - 1037 数字三角形(DP)

数字三角形问题描述小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出

落日映苍穹つ/ 2022年05月18日 10:17/ 0 赞/ 240 阅读