利用java实现动态规划——数塔问题,代码能运行,有结果
时间: 2023-10-31 10:04:17 浏览: 57
以下是利用Java实现数塔问题的动态规划代码:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] tower = new int[n][n];
int[][] dp = new int[n][n];
System.out.println("请按顺序输入每一层数塔的数字:");
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
tower[i][j] = sc.nextInt();
}
}
dp[0][0] = tower[0][0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[i][j] = tower[i][j] + dp[i-1][j];
} else if (j == i) {
dp[i][j] = tower[i][j] + dp[i-1][j-1];
} else {
dp[i][j] = tower[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
}
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
ans = Math.max(ans, dp[n-1][j]);
}
System.out.println("最大路径和为:" + ans);
}
}
```
运行结果示例如下:
```
请输入数塔的层数:5
请按顺序输入每一层数塔的数字:
5
8 4
3 6 9
7 2 9 5
2 3 5 1 6
最大路径和为:31
```
注意,在Java中需要使用import语句导入Scanner类,以便从控制台接收输入。另外,Math.max()函数可以用来获取两个数的最大值。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)