图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。 c++完整代码
时间: 2023-06-08 15:06:18 浏览: 93
由于题目中给定的数字三角形比较简单,我们可以使用暴力的方式来解决这道问题。具体步骤如下:
1. 先将数字三角形存储到一个二维数组中。
2. 从数字三角形的底部往上遍历。对于每一个数字,计算出它左下角和右下角的数字中的最大值。
3. 把当前数字与它下面一层的最大值相加,然后存储到当前数字的位置上。
4. 继续往上遍历,直到遍历到数字三角形的顶部。
5. 最后遍历顶部的所有数字,找到它们中的最大值即可。
下面是完整代码:
```
#include <stdio.h>
#define MAX_N 105
int n;
int triangle[MAX_N][MAX_N];
int main() {
// 读入数字三角形
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &triangle[i][j]);
}
}
// 从下往上遍历
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
int max_child = triangle[i+1][j] > triangle[i+1][j+1] ? triangle[i+1][j] : triangle[i+1][j+1];
triangle[i][j] += max_child;
}
}
// 找到最大的和
int max_sum = triangle[1][1];
for (int j = 2; j <= n; j++) {
if (triangle[1][j] > max_sum) {
max_sum = triangle[1][j];
}
}
printf("%d\n", max_sum);
return 0;
}
```
注意:这个程序只是对输入数据少于 100 行的数字三角形有效,如果输入数据较大,需要进行优化。