蓝桥杯算法训练 ALGO-124 数字三角形

太过爱你忘了你带给我的痛 2023-10-06 09:38 25阅读 0赞

算法训练 数字三角形

时间限制：1.0s 内存限制：256.0MB

问题描述

（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路  
　径，使该路径所经过的数字的总和最大。  
　　●每一步可沿左斜线向下或右斜线向下走；  
　　●1＜三角形行数≤100；  
　　●三角形中的数字为整数0，1，…99；  
　　 ![format_png][].  
　　（图３.１－１）

输入格式

文件中首先读到的是三角形的行数。  
  
　　接下来描述整个三角形

输出格式

最大总和（整数）

样例输入

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

样例输出

**题目解析：**

**　　**

**　　将数字三角形放在二维数组中。从倒数第二行开始逐行往上，每个数都加上它的下一行同一列和下一行右列** **中最大的那一个数。**

**　　路径最大和即为数组中第一个数。**

示例代码：

1 import java.io.BufferedReader;
     2 import java.io.IOException;
     3 import java.io.InputStreamReader;
     4 
     5 public class Main {
     6     private static int row;  //行数
     7     private static int[][] arr;
     8     public static void main(String[] args) throws NumberFormatException, IOException {
     9         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    10         row = Integer.parseInt(br.readLine());
    11         arr = new int[row][row];
    12         
    13         for(int i = 0; i < row; i++){
    14             String[] str = br.readLine().split(" ");
    15             for(int j = 0; j <= i; j++){
    16                 arr[i][j] = Integer.parseInt(str[j]);
    17             }
    18         }
    19         
    20         int maxSum = maxSum(row,arr);
    21         
    22         System.out.println(maxSum);
    23     }
    24     /**
    25      * 最大和
    26      * @param row  行数
    27      * @param arr  数组
    28      * @return     该路径的最大和
    29      */
    30     private static int maxSum(int row, int[][] arr) {
    31         for(int i = row-2; i >= 0; i--){
    32             for(int j = 0; j <= i; j++){
    33                 arr[i][j] += maxNum(arr[i+1][j] , arr[i+1][j+1]);
    34             }
    35         }
    36         return arr[0][0];
    37     }
    38     
    39     /**
    40      * 求两个数中的最大数
    41      * @param a
    42      * @param b
    43      * @return    最大数
    44      */
    45     private static int maxNum(int a, int b) {
    46         return a>b?a:b;
    47     }
    48 }

[format_png]: http://imgconvert.csdnimg.cn/aHR0cDovL2x4LmxhbnFpYW8uY24vUmVxdWlyZUZpbGUuZG8_ZmlkPTlSZEF5NkJl?x-oss-process=image/format,png