AcWing 898. 数字三角形
原题链接
简单
作者:
乾巧
,
2024-04-07 12:13:33
,
所有人可见
,
阅读 1
import java.util.Scanner;
public class Main {
private static final int N = 510;
private static final int INF = 1000000000;
private static int n;
private static int[][] a = new int[N][N];
private static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
a[i][j] = scanner.nextInt();
}
}
// 初始化f数组为-INF
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i + 1; j++) {
f[i][j] = -INF;
}
}
// 初始化f[1][1]
f[1][1] = a[1][1];
// 动态规划求解
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
f[i][j] = Math.max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
}
}
// 找出f[n][i]中的最大值
int res = -INF;
for (int i = 1; i <= n; i++) {
res = Math.max(res, f[n][i]);
}
// 输出结果
System.out.println(res);
scanner.close();
}
}