数字三角形(DP)

约定不等于承诺〃 2022-06-10 05:18 131阅读 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 条评论，131人围观）

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

相关阅读

相关数字三角形

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

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

相关数字三角形

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

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

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

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

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

相关【基础练习】【棋盘DP】codevs2193 数字三角形ww题解

转载请注明出处 CSDN ametake版权所有题目描述 Description 数字三角形必须经过某一个点，使之走的路程和最大输入描述 Input Descript

矫情吗；*/ 2022年08月03日 00:28/ 0 赞/ 113 阅读

相关数字三角形

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

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

相关数字三角形(DP)

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

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

相关数字三角形问题

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

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

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

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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