动态规划数塔问题java
时间: 2023-12-02 12:43:11 浏览: 56
以下是动态规划数塔问题的Java代码实现:
```java
public class NumberTower {
public static void main(String[] args) {
int[][] tower = {{9}, {12, 15}, {10, 6, 8}, {2, 18, 9, 5}, {19, 7, 10, 4, 16}}; // 数塔
int[][] maxSum = new int[tower.length][tower.length]; // 用于存储最大和的数组
// 初始化最后一行
for (int i = 0; i < tower[tower.length - 1].length; i++) {
maxSum[tower.length - 1][i] = tower[tower.length - 1][i];
}
// 从倒数第二行开始向上递推
for (int i = tower.length - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
maxSum[i][j] = Math.max(maxSum[i + 1][j], maxSum[i + 1][j + 1]) + tower[i][j];
}
}
System.out.println("最大和为:" + maxSum[0][0]); // 输出最大和
}
}
```