AcWing 898. 数字三角形
原题链接
简单
作者:
crayon不小心
,
2021-01-13 20:06:56
,
所有人可见
,
阅读 309
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//初始化数组
final int N = 510;
int [][] array = new int[N][N];
//打印数字数字三角形
int n = sc.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <=i; j++) {
array[i][j] = sc.nextInt();
}
}
// System.out.println(arrayList);
//算法介绍
/* 从数组的最低端开始往上走 避免边界判定的额外情况
* 除去起始位置f[1][1] 外循环4次 内循环依据所在行的列数确定
* 每一次内循环都会确定到达上一层指定点的最大距离
*/
for (int i = n-1; i>0; i--) {
for (int j = 1; j <=i ; j++) {
array[i][j]+=Math.max(array[i + 1][j],array[i + 1][j + 1]);
}
}
System.out.println(array[1][1]);
}
}