用动态规划算法解决数字三角形问题从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。Java 完整代码
时间: 2024-02-19 20:59:28 浏览: 32
好的,以下是用 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[][] triangle = new int[n][n]; // 二维数组表示数字三角形
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
triangle[i][j] = scanner.nextInt();
}
}
int[][] dp = new int[n][n]; // 二维数组表示从顶部出发到当前位置的最大路径和
dp[0][0] = triangle[0][0];
for (int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + triangle[i][0]; // 最左侧的位置只能从上侧转移过来
for (int j = 1; j < i; j++) {
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]; // 中间位置可以从上侧左侧转移过来
}
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i]; // 最右侧的位置只能从上侧左侧转移过来
}
int maxSum = dp[n - 1][0];
for (int i = 1; i < n; i++) {
maxSum = Math.max(maxSum, dp[n - 1][i]); // 找到最后一行的最大路径和
}
System.out.println(maxSum);
}
}
```
在这个代码中,我们首先读入数字三角形的行数和每个位置的值,然后定义一个二维数组 `dp` 表示从顶部出发到当前位置的最大路径和。然后我们进行动态规划转移,对于每个位置,它可以从上侧或者左上侧转移过来,最后找到最后一行的最大路径和即可。