题目描述
数字三角形问题
算法1
(暴力枚举) $O(n^2)$
import java.util.;
import java.lang.;
class Main{
public static void main (String[] args){
int [][] arr = new int[505][505];
int [] path = new int[505];
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
if(n>0 && n <=500){
//初始化输入的数字三角形
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
arr[i][j]=sc.nextInt();
}
}
//自底向上比较路径大小
for(int i=n;i>=1;i--){
for(int j =1;j<=i;j++){
path[j]=Math.max(path[j+1],path[j])+arr[i][j];
}
}
System.out.println(path[1]);
}
}
}