第1关:数塔问题 300 学习内容 参考答案 记录 评论 任务描述 相关知识 编程要求 解题思路: 测试说明 任务描述 本关任务:编写用动态规划解决数塔问题 相关知识 为了完成本关任务,你需要掌握:动态规划。 编程要求 , 求上图从顶层到底层的一个路径,使路径上的数字和最大。要求输出最大的数字和max和数值和最大的路径。 解题思路: 原始信息有层数和数塔中的数据,层数用一个整型变量n存储,数塔中的数据用二维数组data,存储成如下的下三角阵: 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 必需用二维数组d存储各阶段的决策结果。二维数组d的存储内容如下: d[n][j]=data[n][j], j=1,2,……,n; d[i][j]=max(d[i+1][j],d[i+1][j+1])+data[i][j], i=n-1,n-2,……1,j=1,2,……,i 最后d[1][1]存储的就是问题的结果。 测试说明 平台会对你编写的代码进行测试: 测试输入: 5 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出示例: max=59 数值和最大的路径是:9->12->10->18->10
时间: 2025-03-31 19:08:27 浏览: 56
### 动态规划解决数塔问题
动态规划是一种通过分解复杂问题并存储中间结果来优化计算效率的方法。对于数塔问题,其核心在于找到从顶部到底部的一条路径,使该路径上数值的总和达到最大。
#### 数塔问题的核心思路
假设有一个三角形数塔,每一层都有固定的数字排列。定义状态 `dp[i][j]` 表示到达第 i 层第 j 个节点的最大路径和,则可以通过以下递推关系求解:
\[ dp[i][j] = \text{max}(dp[i-1][j], dp[i-1][j-1]) + \text{triangle}[i][j] \]
其中:
- \( dp[i-1][j] \) 和 \( dp[i-1][j-1] \) 是当前节点上方两个可能的父节点。
- \( triangle[i][j] \) 是数塔中对应位置的实际值[^1]。
边界条件为当某一层只有一个节点时,直接继承其值作为初始状态。
以下是基于此逻辑的具体实现代码:
```java
public class NumberTower {
public static int maxPathSum(int[][] triangle) {
int n = triangle.length;
// 创建 DP 数组用于保存每一步的状态
int[][] dp = new int[n][];
for (int i = 0; i < n; i++) {
dp[i] = new int[triangle[i].length];
}
// 初始化最后一层的数据到DP表中
for (int j = 0; j < triangle[n - 1].length; j++) {
dp[n - 1][j] = triangle[n - 1][j];
}
// 自底向上填充DP表
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < triangle[i].length; j++) {
dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
// 返回起点处的结果
return dp[0][0];
}
public static void main(String[] args) {
int[][] tower = {
{7},
{3, 8},
{8, 1, 0},
{2, 7, 4, 4},
{4, 5, 2, 6, 5}
};
System.out.println("最大路径和:" + maxPathSum(tower));
}
}
```
以上程序实现了自底向上的动态规划过程,最终返回的是从顶端至底部的最大路径和。
---
###
阅读全文
相关推荐

















