Java输出数字三角形

时间:2022-05-23 盛世如念人气:0

题目:

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

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

输入格式

第一行包含整数 nn，表示数字三角形的层数。

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

输出格式

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

数据范围

1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000

输入样例：

输出样例：

题解:

相对于二维数组来看，每一个数只能往下放或者右下方走，发现从下往上走更加方便实现。我们反向思考，从下或者右下方走，如果我们每次都知道了某数的下放和右下方谁最大了呢?

每次从最后行的相邻两个数比较谁最大，把每次最大的加到第一个数的上方，这样数组的第一行第一个数就是最大值了。

例如:

代码:

 
 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int nums[][] = new int[n][];
        for(int i = 0;i<n;i++){
            nums[i] = new int[i+1];
            for(int j = 0;j<i+1;j++){
                nums[i][j] = sc.nextInt();
 
            }
        }
        for(int i =n-1 ;i>0;i--){
            for(int j = 0;j<nums[i].length-1;j++){
                nums[i-1][j] += Math.max(nums[i][j],nums[i][j+1]);
            }
        }
        System.out.println(nums[0][0]);
 
 
 
    }
 
}

总结

加载全部内容