一、实验目的: 1、掌握动态规划算法的基本思想; 2、掌握最优子结构性质和基于表格的最优值计算方法; 二、实验内容与步骤: 有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?给出C语言完整代码
时间: 2024-03-14 14:42:50 浏览: 10
好的,下面是使用C语言实现的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100
// 数塔
int tower[MAX_N][MAX_N];
// 记忆化数组
int memo[MAX_N][MAX_N];
// 数塔问题的动态规划函数
int dp(int i, int j, int n) {
// 如果已经计算过了,直接返回结果
if (memo[i][j] != -1) {
return memo[i][j];
}
// 到达底部
if (i == n - 1) {
return memo[i][j] = tower[i][j];
}
// 递归计算
int left = dp(i + 1, j, n);
int right = dp(i + 1, j + 1, n);
// 取左右路径中的较大值
return memo[i][j] = tower[i][j] + (left > right ? left : right);
}
int main() {
int n;
printf("请输入数塔的高度:");
scanf("%d", &n);
// 输入数塔
printf("请输入数塔:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
scanf("%d", &tower[i][j]);
memo[i][j] = -1; // 初始化记忆化数组
}
}
// 动态规划求解
int ans = dp(0, 0, n);
printf("经过的结点的数字之和最大为:%d\n", ans);
return 0;
}
```
这里使用了记忆化搜索的方式求解数塔问题,通过递归计算每个结点到底部的最大路径和,并将计算结果缓存到记忆化数组中,避免重复计算。最后返回第一个结点到底部的最大路径和即可。