数字三角形题解【DP】数字三角形

140 阅读 0 评论 93 点赞

我是靠谱客的博主单纯招牌，这篇文章主要介绍数字三角形题解【DP】数字三角形，现在分享给大家，希望可以做个参考。

文章目录

数字三角形
- 分析
- 代码
- 运行结果

数字三角形

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

复制代码

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

输入格式
第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：

复制代码

输出样例：

复制代码

1
2
30

分析

在这里插入图片描述

但是在这我们可以调整一下由下往上推，因为如果是从上往下的话要进行一些特判，这样就有点麻烦了，直接看代码吧！！！

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510;
int dp[N][N];
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> dp[i][j];
		}
	}
	for (int i = n - 1; i; i--) {
		for (int j = 1; j <= i; j++) {
			dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);
		}
	}
	
	cout << dp[1][1] << endl;
	return 0;
}