从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大,用Java代码实现
时间: 2024-01-05 07:02:30 浏览: 27
这个问题可以使用动态规划算法来解决。我们可以从倒数第二行开始,对于每个结点,计算它到底层的最大路径和,然后将这个最大值更新到该结点上。最后,最大路径和就是顶部结点的值。
具体实现如下:
```java
public class MaxPathSum {
public static int maxPathSum(int[][] triangle) {
int n = triangle.length;
int[] dp = new int[n];
// 初始化dp数组为最后一行的值
for (int i = 0; i < n; i++) {
dp[i] = triangle[n - 1][i];
}
// 从倒数第二行开始,逐层计算最大路径和
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
// 选择左右两个子结点中较大的那个
dp[j] = Math.max(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
public static void main(String[] args) {
int[][] triangle = {{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}};
System.out.println(maxPathSum(triangle)); // 输出:20
}
}
```
在上面的代码中,我们使用了一个一维数组来存储每个结点到底层的最大路径和,从倒数第二层开始,逐层向上计算。在计算每个结点的最大路径和时,我们选择其左右两个子结点中较大的那个,并加上当前结点的值,更新到dp数组中。最终,最大路径和就是顶部结点的值,也就是dp[0]。