用C语言写:从顶部出发,每一个节点都可以选择向左或者向右走,一直走到底层,要求走过的路径上的值最大上
时间: 2024-02-18 11:00:53 浏览: 63
这道题是一个经典的动态规划问题,可以使用递归或者迭代的方式来解决。以下是一个使用递归的C语言代码示例:
```c
#include <stdio.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))
int triangle[5][5] = {
{5},
{7, 8},
{2, 3, 4},
{4, 9, 6, 1},
{2, 7, 9, 4, 5}
};
int max_path(int row, int col) {
if (row == 4) { // 到达底层,返回节点值
return triangle[row][col];
} else {
int left_path = max_path(row+1, col); // 向左走的最大路径和
int right_path = max_path(row+1, col+1); // 向右走的最大路径和
return triangle[row][col] + MAX(left_path, right_path); // 返回当前节点值和最大路径和之和
}
}
int main() {
int result = max_path(0, 0); // 从顶部出发,计算最大路径和
printf("The maximum path sum is %d\n", result);
return 0;
}
```
这个示例中,我们使用一个二维数组 `triangle` 来表示三角形,其中 `triangle[i][j]` 表示第 `i` 行、第 `j` 列的节点值。我们从顶部出发,调用 `max_path()` 函数来计算最大路径和。如果当前节点位于底层,直接返回节点值;否则,递归计算向左或向右走的最大路径和,并返回当前节点值和最大路径和之和。最后,我们在 `main()` 函数中输出计算结果。
输出结果为:
```
The maximum path sum is 30
```
这意味着,从顶部出发,我们可以得到一条值为 30 的最大路径和。
阅读全文