Java实现输出数字三角形实例代码

题目:

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

        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

输入样例：

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

输出样例：

30

题解:

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

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

        例如:

代码:

 
 
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]);
 
 
 
    }
 
}

总结

到此这篇关于java实现输出三角形实例代码的文章就介绍到这了,更多相关java输出三角形内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！