AcWing 898. 数字三角形
原题链接
简单
作者:
hhu-菜菜
,
2021-05-19 21:29:08
,
所有人可见
,
阅读 207
import java.util.Scanner;
class Main{
static final int N = 510;
static int n;
static int[][] a = new int[N][N];
static int[][] dp = new int[N][N];
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
a[i][j] = reader.nextInt();
}
}
//因为这里的元素有负的,所以把所有的设置成最小值
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
dp[i][j] = Integer.MIN_VALUE;
}
}
dp[1][1] = a[1][1];
reader.close();
for(int i = 2;i <= n;i++){
for(int j = 1;j <= i;j++){
dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
}
}
//最后一行都是最大值,找到其中的最大值就可以了
int res = Integer.MIN_VALUE;
for(int i = 1;i <= n;i++){
res = Math.max(res,dp[n][i]);
}
System.out.println(res);
}
}