如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大。记忆递归算法实现,数塔的数据从下标为1的位置开始存放 用c语言
时间: 2024-03-16 15:46:32 浏览: 56
C语言实现递归算法
好的,这是一个经典的动态规划问题。记忆递归算法的实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
int max(int a, int b) {
return (a > b) ? a : b;
}
int max_sum(int i, int j, int triangle[][MAX_N+1], int memo[][MAX_N+1]) {
if (i == 0) {
return triangle[0][1];
}
if (memo[i][j] != -1) {
return memo[i][j];
}
int left = max_sum(i-1, j-1, triangle, memo);
int right = max_sum(i-1, j, triangle, memo);
memo[i][j] = max(left, right) + triangle[i][j];
return memo[i][j];
}
int main() {
int n, triangle[MAX_N+1][MAX_N+1], memo[MAX_N+1][MAX_N+1];
memset(memo, -1, sizeof(memo));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &triangle[i][j]);
}
}
int max_path_sum = 0;
for (int j = 1; j <= n; j++) {
max_path_sum = max(max_path_sum, max_sum(n, j, triangle, memo));
}
printf("%d\n", max_path_sum);
return 0;
}
```
其中,`max` 函数用于求两个整数的最大值。`max_sum` 函数通过递归调用自身,计算每个节点的最大路径和,并将结果存储在 `memo` 中,以便下次使用时直接调用,避免重复计算。函数的参数包括 `i` 和 `j` 表示当前节点的行号和列号,`triangle` 是存储数塔数据的二维数组,`memo` 是用于记忆化的二维数组,初始化为 `-1`。最终返回数塔底部的最大路径和。
在 `main` 函数中,程序首先读入数塔数据并存储在 `triangle` 数组中,然后遍历每个底部节点,分别计算从该节点出发的最大路径和,并取最大值作为最终结果输出。注意,由于 C 语言中二维数组的下标从 0 开始,因此程序中的 `i` 和 `j` 都需要减一。
调用方式如下:
```
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```
输出结果为 `30`,即从顶部出发的最大路径和。
阅读全文