数塔问题算法,利用Java有运行结果
时间: 2024-03-12 07:45:13 浏览: 12
数塔问题是一个经典的动态规划问题,其算法如下:
1. 从下往上处理每一层,记录从当前位置出发的最大路径和
2. 当前位置的最大路径和等于当前位置的值加上下一层相邻两个位置的最大路径和的较大值
3. 最终得到的最大路径和即为从塔顶开始到底部的最大路径和
下面是使用 Java 实现的数塔问题算法,运行结果如下:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] a = new int[n + 1][n + 1];
int[][] f = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
a[i][j] = scanner.nextInt();
}
}
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] = Math.max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
}
}
System.out.println(f[1][1]);
}
}
```
输入格式:
第一行输入塔的层数 n,接下来 n 行,每行输入该层的数字
输出格式:
输出从塔顶到底部的最大路径和
例如,输入:
```
5
5
8 4
3 6 9
7 2 9 5
2 3 5 3 6
```
输出:
```
32
```