蓝桥杯

题目描述

题目来源
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。

输入描述
输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。

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

输入输出样例
示例
输入

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

输出

30

采用递推，第i行，第j列，通过左上过来，或者通过右上过来，取他们的最大值，即是到达该点的最大路径，递推式： a[i][j] += Math.max(a[i - 1][j - 1], a[i - 1][j])；找最后一行的最大值即可

import java.util.Scanner;

// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[][] a = new int[105][105];
        int n = scan.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++)
                a[i][j] = scan.nextInt();
        }
        //从第二行开始
        for (int i = 2; i <= n; i++)
            for (int j = 1; j <= i; j++)
            	//从左上或右上其中一条路过来，不能把左上右上两个全部累加上去，因为是找路径
                a[i][j] += Math.max(a[i - 1][j - 1], a[i - 1][j]);
        int max = a[n][1];
        for (int i = 2; i <= n; i++)
            max = a[n][i] > max ? a[n][i] : max;
        System.out.println(max);
        scan.close();
    }
}