数字三角形（JAVA）

题目

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。

下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

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

输出

27

运行限制

-最大运行时间：1S

-最大运行内存：256M

代码

import java.util.Scanner;
 
public class main {
    public static void main(String[] args) {
 
        Scanner scan = new Scanner(System.in);
        int N=scan.nextInt();
        int[][] arr=new int [N][N];   //二维数组arr储存数字三角形
        int[][] pre=new int[N][N];   //二维数组pre储存路径，初始为零向左走减1向右走加1
        int[][] dp=new int[N][N];    //二维数组dp储存走到对应位置的最大和
        for (int i=0;i<N;i++){
            for (int a=0;a<=i;a++){
                arr[i][a]=scan.nextInt();
                pre[i][a]=0;
            }
        }
        dp[0][0]=arr[0][0];//三角形顶点最大和就是它本身
        for (int i=1;i<N;i++){
            dp[i][0]=dp[i-1][0]+arr[i][0];
            pre[i][0]=pre[i-1][0]-1;
        }                            //只有通过arr[i-1][0]才能到达arr[i][0]
        for (int i=1;i<N;i++){
            dp[i][i]=dp[i-1][i-1]+arr[i][i];
            pre[i][i]=pre[i-1][i-1]+1;
        }                             //只有通过arr[i-1][i-1]才能到达arr[i][i]
        for (int i=1;i<N;i++){
            for (int j=1;j<i;j++){
                if (dp[i-1][j-1]>dp[i-1][j]){
                    pre[i][j]=pre[i-1][j-1]+1;
                    dp[i][j]=arr[i][j]+dp[i-1][j-1];
                }                     
                else{
                    pre[i][j]=pre[i-1][j]-1;
                    dp[i][j]=arr[i][j]+dp[i-1][j];
                }       
 
            }
        }               //arr[i][j]可以从arr[i-1][j-1]或arr[i-1][j]到达所以要比较找出最大值
        int[] sum=new int [N];   //定义sum数组储存到达最底部符合条件的和初始为零
        for (int i=0;i<N;i++){
            sum[i]=0;
            if (pre[N-1][i]<=1&&pre[N-1][i]>=-1){
                sum[i]=dp[N-1][i];
            }                  //pre二维数组记录路径只要为-1，0，1三个数就说明向左下和右下走的次数不超过1，记录数据最终进行比较
 
        }
        int max=sum[0];
        for (int i=0;i<N;i++){
            if(max<sum[i]){
                max=sum[i];
            }
            else{
                max=max;
            }
        }                  
        System.out.println(max);     //通过比较选出最大路径并输出
        scan.close();
    }
}