Introduction

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

7

3 8

8 1 0

2 7 4 4

Input

第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i行表示数字三角形第i 层包含的整数。

所有输入整数绝对值小于20

Output

输出一个整数，表示最大的路径数字和。

Sample

input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

output

30

Solution

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[][] arr=new int[n][n];
        int num=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<num;j++){
                arr[i][j]=s.nextInt();
            }
            num++;
        }
        for(int i=n-1;i>=0;i--){
            if(i==n-1)continue;
            for(int j=0;j<=i;j++){
                arr[i][j]=Math.max(arr[i+1][j],arr[i+1][j+1])+arr[i][j];
            }
        }
        System.out.println(arr[0][0]);
    }
}

Experience

很久没用dp，第一时间竟然忘记怎么写了，哎。