题目：数字三角形
题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和。
输入：第一行值n，代表n行数值；后面的n行数据代表每一行的数字。
输出：经过数字的最大和。
例：
输入：
4
1
3 2
4 10 1
4 3 2 20
输出：
24
分析：这也是一个典型的贪心算法无法解决的问题，同样可以用动态规划（dp算法）来解决。把边界数字首先初始化到结果矩阵中，再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形，与传统的状态方程相比需要做点改进。
数组编号：
状态方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>using namespace std;int main(){ int i; int n; cin >> n; int **p = new int *[n]; for (i = 0; i < n; i++) { p[i] = new int[n]; } for (i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cin >> p[i][j]; } } for (i = 1; i < n; i++) { p[i][0] += p[i - 1][0]; } for (i = 1; i < n; i++) { p[i][i] += p[i - 1][i - 1]; } for (i = 2; i < n; i++) { for (int j = 1; j < i; j++) { p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j]; } } for (i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cout << p[i][j] << " "; } cout << endl; }} |
结果如下图：
所以最下层的数字和最大值是24.
总结
以上所述是小编给大家介绍的C++数字三角形问题与dp算法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！
原文链接：https://www.cnblogs.com/ljy1227476113/archive/2018/09/02/9572328.html
