数塔求最大值路径用c++语言写出来
时间: 2023-08-17 19:04:05 浏览: 42
好的,以下是使用 C++ 语言实现数塔求最大值路径的代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int tower[MAXN][MAXN];
int max_vals[MAXN];
int main() {
int n;
cin >> n;
// 输入数塔
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> tower[i][j];
}
}
// 从塔底开始初始化最大值数组
for (int j = 1; j <= n; j++) {
max_vals[j] = tower[n][j];
}
// 从倒数第二行开始向上推导
for (int i = n-1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
// 计算当前位置的最大值
max_vals[j] = tower[i][j] + max(max_vals[j], max_vals[j+1]);
}
}
// 输出最大值
cout << max_vals[1] << endl;
return 0;
}
```
该代码使用了动态规划算法,与前面 Python 代码的思路相同。区别在于,C++ 中数组下标从 0 开始,而 Python 中数组下标从 1 开始,因此在代码中需要对下标进行一些调整。
输入格式为:
```
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```
其中第一行为数塔的高度,接下来 n 行为数塔的每一行,每行包含 i 个数字,表示数塔中的数值。
输出为数塔的最大值路径的和。
希望能对你有所帮助!