从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。C语言
时间: 2023-12-11 16:04:14 浏览: 33
这是一个经典的动态规划问题,可以使用递归或者循环的方式解决。以下是使用循环的C语言代码:
```c
#include<stdio.h>
#define N 5 // 金字塔的层数
int main()
{
int arr[N][N] = {
{5,0,0,0,0},
{7,8,0,0,0},
{2,3,4,0,0},
{4,9,6,1,0},
{2,7,9,4,5}
};
int dp[N][N] = {0}; // 动态规划数组,dp[i][j]表示从顶部到第i行第j列的最大值
// 初始化第一行
dp[0][0] = arr[0][0];
for(int j=1;j<N;j++) {
dp[0][j] = dp[0][j-1] + arr[0][j];
}
// 动态规划
for(int i=1;i<N;i++) {
for(int j=0;j<=i;j++) {
if(j == 0) { // 左边界,只能从上面一格过来
dp[i][j] = dp[i-1][j] + arr[i][j];
} else if(j == i) { // 右边界,只能从上面一格过来
dp[i][j] = dp[i-1][j-1] + arr[i][j];
} else { // 中间部分,可以从上面一格或者上面左边一格过来,取较大值
int max_prev = (dp[i-1][j] > dp[i-1][j-1]) ? dp[i-1][j] : dp[i-1][j-1];
dp[i][j] = max_prev + arr[i][j];
}
}
}
// 找出最大值
int max = dp[N-1][0];
for(int j=1;j<N;j++) {
if(dp[N-1][j] > max) {
max = dp[N-1][j];
}
}
printf("最大值为:%d\n", max);
return 0;
}
```
该代码中,我们首先定义了一个二维数组`arr`来表示金字塔,每一行从左往右依次表示该行每个结点的值,每行末尾用0填充。然后定义了一个同样大小的二维数组`dp`来表示动态规划过程中的状态,其中`dp[i][j]`表示从顶部到第i行第j列的最大值。接着,我们使用一个双重循环来进行动态规划,先对第一行进行初始化,然后从第二行开始,对每个结点进行计算。对于每个结点,我们需要考虑它只能从上面一格过来、只能从上面左边一格过来、或者可以从上面一格或者上面左边一格过来这三种情况,分别计算出每种情况的值,取其中的最大值即可。最后,我们再遍历最后一行的所有结点,找出其中的最大值即为所求。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)