如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大。(分别使用动态规划算法和记忆递归算法实现,数塔的数据从下标为1的位置开始存放),用C语言实现
时间: 2024-03-16 12:45:51 浏览: 17
好的,以下是动态规划和记忆递归算法使用C语言实现的代码。
动态规划算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
int f[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int max_path_sum(int n, int a[][MAX_N]) {
// 初始化状态
f[1][1] = a[1][1];
// 状态转移
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = max(f[i-1][j], f[i-1][j+1]) + a[i][j];
}
}
// 返回最大路径和
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, f[n][i]);
}
return ans;
}
int main() {
int n;
int a[MAX_N][MAX_N];
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
printf("%d\n", max_path_sum(n, a));
return 0;
}
```
记忆递归算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
int mem[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int dfs(int i, int j, int n, int a[][MAX_N]) {
if (i == n) {
return a[i][j];
}
if (mem[i][j] != 0) {
return mem[i][j];
}
int left = dfs(i+1, j, n, a);
int right = dfs(i+1, j+1, n, a);
mem[i][j] = max(left, right) + a[i][j];
return mem[i][j];
}
int max_path_sum(int n, int a[][MAX_N]) {
// 初始化状态
mem[1][1] = a[1][1];
// 计算最大路径和
return dfs(2, 1, n, a);
}
int main() {
int n;
int a[MAX_N][MAX_N];
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
printf("%d\n", max_path_sum(n, a));
return 0;
}
```
以上就是使用C语言实现动态规划和记忆递归算法解决数塔问题的代码。