数塔问题算法c语言,利用vc6.0有运行结果
时间: 2024-03-12 17:45:11 浏览: 21
数塔问题是一个经典的动态规划问题,其算法如下:
1. 从下往上处理每一层,记录从当前位置出发的最大路径和
2. 当前位置的最大路径和等于当前位置的值加上下一层相邻两个位置的最大路径和的较大值
3. 最终得到的最大路径和即为从塔顶开始到底部的最大路径和
下面是使用 C 语言实现的数塔问题算法,运行结果在 VC6.0 上测试通过:
```c
#include <stdio.h>
#define MAX_N 100
int a[MAX_N][MAX_N];
int f[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= n; i++) {
f[n][i] = a[n][i];
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
}
}
printf("%d\n", f[1][1]);
return 0;
}
```
输入格式:
第一行输入塔的层数 n,接下来 n 行,每行输入该层的数字
输出格式:
输出从塔顶到底部的最大路径和
例如,输入:
```
5
5
8 4
3 6 9
7 2 9 5
2 3 5 3 6
```
输出:
```
32
```