数字三角形问题

灰太狼 2022-02-16 02:14 240阅读 0赞

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。  
![1730.png][]  
对于给定的由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 <iostream>
    #include <math.h>
    #include <vector>
    #define MAX 1000
    
    using namespace std;
    
    int Data[MAX + 1][MAX + 1];
    int dp[MAX + 1][MAX + 1];
    
    int max(int a, int b) {
    	return a > b ? a : b;
    }
    void getmax(int n) {
    	//dp初始化  把dp的最后一行初始化为数字三角形最后一行的数
    	for (int i = 0; i < n; i++) {
    		dp[n - 1][i] = Data[n - 1][i];
    	}
    	int tempmax;
    	//从倒数第二行开始  往上找
    	for (int i = n - 2; i >= 0; i--) {
    		for (int j = 0; j <= i; j++) {
    			//找dp[i][j]的下方和右下方中较大的那一个
    			tempmax = max(dp[i + 1][j], dp[i + 1][j + 1]);
    			dp[i][j] = tempmax + Data[i][j];
    		}
    	}
    }
    
    int main() {
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < i+1; j++) {
    			cin >> Data[i][j];
    		}
    	}
    	getmax(n);
    	cout << dp[0][0] << endl;
    	return 0;
    }

[1730.png]: https://acm.sdut.edu.cn/image/1730.png

发表评论取消回复

表情：

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

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

相关阅读

相关数字三角形

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

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

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

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

相关数字三角形问题

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

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

相关数字三角形问题

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

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

相关数字三角形问题

数字三角形问题 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 赞/ 241 阅读

相关 1730 数字三角形问题

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

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