数字三角形问题:要求从顶部出发,在每一个结点可以选择从左走或者从右走直走到底层。试设计一个算法,计算从三角形的从顶至底的一条路径,使该路径经过的数字总和最大 才c++代码实现
时间: 2024-05-07 22:19:35 浏览: 15
以下是一个动态规划的解法,时间复杂度为O(n^2),其中n为数字三角形的行数。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> triangle(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cin >> triangle[i][j];
}
}
// dp[i][j]表示从顶部到位置(i,j)的最大数字和
vector<vector<int>> dp(n, vector<int>(n));
dp[0][0] = triangle[0][0];
// 从第2行开始逐行计算
for (int i = 1; i < n; i++) {
// 计算每一行的第一个数字和最后一个数字
dp[i][0] = dp[i - 1][0] + triangle[i][0];
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
// 计算中间的数字
for (int j = 1; j < i; j++) {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
}
// 找到最大数字和
int max_sum = 0;
for (int i = 0; i < n; i++) {
max_sum = max(max_sum, dp[n - 1][i]);
}
cout << max_sum << endl;
return 0;
}
```
输入格式:第一行为数字三角形的行数n,接下来n行每行为数字三角形的一行。
输出格式:一个整数,表示从顶部到底部的最大数字和。
样例输入:
```
5
5
8 4
3 6 9
7 2 5 1
4 9 3 8 5
```
样例输出:
```
27
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)