用c++写一个观察下面的数字金字塔。 用动态规划法设计一个算法来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
时间: 2024-01-01 11:06:33 浏览: 45
好的,这是一道典型的动态规划题目。我们可以设计一个二维数组dp[i][j]表示从最高点到(i,j)这个位置的路径上数字和的最大值,那么我们可以得到状态转移方程:
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
其中triangle[i][j]表示(i,j)这个位置上的数字。这个方程的意思是,到达(i,j)这个位置的最大数字和,要么是从(i-1,j-1)这个位置过来,要么是从(i-1,j)这个位置过来,取两者中的较大值,再加上当前位置的数字。
最后,我们只需要遍历最后一行的所有位置,找到数字和最大的位置即可。
以下是一个简单的C++实现代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int maxSumPath(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
dp[0][0] = triangle[0][0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + triangle[i][j];
} else if (j == i) {
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
} else {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
}
}
}
int maxSum = dp[n - 1][0];
for (int i = 1; i < n; i++) {
maxSum = max(maxSum, dp[n - 1][i]);
}
return maxSum;
}
int main() {
vector<vector<int>> triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
cout << maxSumPath(triangle) << endl;
return 0;
}
```
输出结果为:30
希望这个C++代码能够解决你的问题。
相关推荐
![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)