算法训练数字三角形

旧城等待， 2022-08-18 12:10 131阅读 0赞

问题描述
    　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
    　　径，使该路径所经过的数字的总和最大。
    　　●每一步可沿左斜线向下或右斜线向下走；
    　　●1＜三角形行数≤100；
    　　●三角形中的数字为整数0，1，…99；
    
    
    　　.
    　　（图３.１－１）
    输入格式
    　　文件中首先读到的是三角形的行数。
    
    　　接下来描述整个三角形
    输出格式
    　　最大总和（整数）
    样例输入
    5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    样例输出
    30

提交序号    674864
    作者  李增光
    提交时间    12-18 10:13
    评测结果    正确
    得分  100
    CPU使用   358ms
    内存使用    35.22MB
    试题名称    算法训练 数字三角形
    语言  JAVA

import java.util.Scanner;
    
    public class Main {
    
    
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            int n = s.nextInt();
            //开辟一个二维数组,存放三角型的元素.(非常关键)
            int[][] a = new int[n + 1][n + 1];//存放元素的位置,
            //可以画出一个(n+1)*(n+1)的矩阵,便于理解
            /* * 往二维数组指定位置存放元素 * */
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= i; j++)
                    a[i][j] = s.nextInt();
            /* * 从数组后一行开始,两两比较元素,选出两者较大的与父节点相加.依此类推 * */
            for (int i = n - 1; i > 0; i--)
                for (int j = 1; j <= i; j++)
                    if (a[i + 1][j] > a[i + 1][j + 1])
                        a[i][j] += a[i + 1][j];
                    else
                        a[i][j] += a[i + 1][j + 1];
            //最后顶点存放了最大权路径
            System.out.println(a[1][1]);//
    
        }
    
    }