package test;
import java.util.Scanner;
public class 动态规划 {
/*
* 数字三角形(POJ1163)
在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。 三角形的行数大于1小于等于100,数字为 0 - 99
输入格式:
5 //表示三角形的行数 接下来输入三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求输出最大和
*/
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int map[][]=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
map[i][j]=in.nextInt();
}
}
int ans[][]=new int[n][n];
for(int i=0;i<n;i++){
ans[n-1][i]=map[n-1][i];
}
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
ans[i][j]=Math.max(ans[i+1][j], ans[i+1][j+1])+map[i][j];
}
}
System.out.print(ans[0][0]);
}
}